题目描述

老师想从N名学生中选M人当学霸，但有K对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的M尽可能接近

输入格式

第一行，三个正整数N，M，K。

第2...K行,每行2个数，表示一对实力相当的人的编号(编号为1…N)

输出格式

一行，表示既不让同学们抗议，又与原来的M尽可能接近的选出学霸的数目。(如果有两种方案与M的差的绝对值相等，选较小的一种:)

输入输出样例

输入 #1复制

4 3 21 23 4

输出 #1复制

2

说明/提示

100%的数据N，P<=20000

 

用并查集合并同一水平的人，找出个数，然后背包

 

#include
      
       using namespace std;int n,m,k;int f[20001];int t[20001];int cnt,a[20001];bool u[20001];int ans;int find(int x){    if(f[x]==x) return f[x];    f[x]=find(f[x]);    return f[x];}void merge(int x,int y){    f[find(x)]=f[find(y)];}int main(){    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=n;i++) f[i]=i;    for(int i=1;i<=k;i++)    {        int x,y;        scanf("%d%d",&x,&y);        if(find(x)!=find(y)) merge(x,y);    }    for(int i=1;i<=n;i++) f[i]=find(f[i]);    for(int i=1;i<=n;i++) t[f[i]]++;    for(int i=1;i<=n;i++)    {        if(t[i])        {            a[++cnt]=t[i];        }    }    u[0]=1;    for(int i=1;i<=cnt;i++)    {        for(int j=n-a[i];j>=0;j--)        {            if(u[j]) u[j+a[i]]=1;        }    }    for(int i=1;i<=n;i++)    {        if(u[i]&&abs(ans-m)>abs(i-m)) ans=i;    }    printf("%d",ans);    return 0;}