題目描述
老師想從N名學生中選M人當學霸，但有K對人實力相當，如果實力相當的人中，一部分被選上，另一部分沒有，同學們就會抗議。是以老師想請你幫他求出他該選多少學霸，才能既不讓同學們抗議，又與原來的M盡可能接近
輸入輸出格式
輸入格式：
第一行，三個正整數N，M，K。
第2...K行,每行2個數，表示一對實力相當的人的編号(編号為1…N)
輸出格式：
一行，表示既不讓同學們抗議，又與原來的M盡可能接近的選出學霸的數目。(如果有兩種方案與M的差的絕對值相等，選較小的一種:)
輸入輸出樣例
輸入樣例#1：
4 3 2
1 2
3 4 輸出樣例#1：
2 說明
100%的資料N，P<=20000
對于這道題，我們需要先搞一個并查集把實力相同的人都存進去，這樣我們就可以得到每種實力的人分别有多少個。
把它當成一個01背包（範圍要開到2*m，因為可能有比m大但是大小仍和m相近的答案出現）過一遍
然後我們枚舉在選的人數，始終維護與m內插補點最小的那個。
它就是答案啦！
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1e4 + 3;
int n,m,k;
int f[2*N],dp[2*N],t[2*N],c[2*N];
int ans = 0x7fffffff;
int find(int x)
{
if(f[x] == x)return x;
return f[x] = find(f[x]);
}
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);
int a = find(x);
int b = find(y);
if(a != b)f[a] = b;
}
for(int i = 1;i <= n;i++)f[i] = find(f[i]);
for(int i = 1;i <= n;i++)t[f[i]]++;
int cnt = 0;
for(int i = 1;i <= n;i++)
{
if(t[i] != 0)c[++cnt] = t[i];
}
for(int i = 1;i <= cnt;i++)
{
for(int j = m + m;j >= c[i];j--)
{
dp[j] = max(dp[j],dp[j - c[i]]+c[i]);
}
}
for(int i = 1;i <= n;i++)
{
if(abs(dp[i] - m) < abs(ans - m))ans = dp[i];
}
printf("%d",ans);
return 0;
}