老师想从N名学生中选M人当学霸，但有K对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的M尽可能接近
输入格式：
第一行，三个正整数N，M，K。
第2...K行,每行2个数，表示一对实力相当的人的编号(编号为1…N)
输出格式：
一行，表示既不让同学们抗议，又与原来的M尽可能接近的选出学霸的数目。(如果有两种方案与M的差的绝对值相等，选较小的一种:)
4 3 2 1 2 3 4
2
100%的数据N，P<=20000
并查集+ 背包
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int maxn=200000+5; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int n,m,k,ans; int f[maxn],num[maxn],father[maxn]; int find(int x) { if(x!=father[x]) father[x]=find(father[x]); return father[x]; } inline void merge(int x,int y) { int r1=find(x); int r2=find(y); if(r1!=r2) { father[r2]=r1; num[r1]+=num[r2]; num[r2]=0; } } int main() { n=read();m=read();k=read(); for(int i=1;i<=n;i++) { father[i]=i; num[i]=1;} for(int i=1;i<=k;i++) { int x,y; x=read();y=read(); merge(x,y); } for(int i=1;i<=n;i++) { if(!num[i]) continue; for(int j=2*m;j>=num[i];j--) f[j]=max(f[j],f[j-num[i]]+num[i]); } int minn=m; for(int i=1;i<=2*m;i++) { if((abs(f[i]-m))<minn) { minn=abs(f[i]-m); ans=f[i]; } } printf("%d\n",ans); return 0; }
原文：http://www.cnblogs.com/huihao/p/7523543.html