社区讨论
求hack
P2170选学霸参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo3ipkrq
- 此快照首次捕获于
- 2023/10/24 07:17 2 年前
- 此快照最后确认于
- 2023/10/24 07:17 2 年前
CPP
#include<bits/stdc++.h>
#define maxn 20002
using namespace std;
int n,m,k;
int dp,siz[maxn],dp1;
struct node{
int fa[maxn];
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
}
}
int getfather(int x){
return fa[x]==x?x:fa[x]=getfather(fa[x]);
}
void hb(int x,int y){
int fax=getfather(x);
int fay=getfather(y);
if(fax!=fay){
if(siz[fax]>siz[fay]){
swap(fax,fay);
}
fa[fax]=fay;
siz[fay]+=siz[fax];
}
}
}bcj;
int main(){
scanf("%d%d%d",&n,&m,&k);
bcj.init();
for(int i=1;i<=k;i++){
int x,y;
scanf("%d%d",&x,&y);
bcj.hb(x,y);
}
for(int i=1;i<=n;i++){
if(bcj.getfather(i)==i){
if(abs(m-dp)>abs(m-dp-siz[i]))
dp+=siz[i];
//cout<<abs(m-dp[cnt-1])<<" "<<abs(m-dp[cnt-1]-siz[i])<<endl;
}
}
for(int i=n;i>=0;i--){
if(bcj.getfather(i)==i){
if(abs(m-dp1)>abs(m-dp1-siz[i]))
dp1=dp1+siz[i];
//cout<<abs(m-dp[cnt-1])<<" "<<abs(m-dp[cnt-1]-siz[i])<<endl;
}
}
if(abs(m-dp1)==abs(m-dp)){
printf("%d",min(dp,dp1));
}else if(abs(m-dp1)>abs(m-dp)){
printf("%d",dp);
}else printf("%d",dp1);
return 0;
}
本题正解是dp,但是可以通过正向贪心选一遍,反向贪心选一遍来通过。
求是数据水了还是可以这样做。
回复
共 2 条回复,欢迎继续交流。
正在加载回复...