Portal
Portal1: Luogu
Description
老师想从$N$名学生中选$M$人当学霸，但有$K$对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的$M$尽可能接近。
Input
第一行，三个正整数$N, M, K$。
第$2$至$K$行，每行$2$个数，表示一对实力相当的人的编号（编号为$1 \cdots N$）。
Output
一行，表示既不让同学们抗议，又与原来的$M$尽可能接近的选出学霸的数目。（如果有两种方案与$M$的差的绝对值相等，选较小的一种）
Sample Input
4 3 2
1 2
3 4Sample Output
2Hint
对于$100\%$的数据$N, P \le 20000$。
Solution
这题如果选了一个人，那么与他实力相当的人也要选上。所以我们可以把会产生连锁反应的人都捆起来。不难想到用并查集。
然后我们把一捆一捆的总价值记录下来，做一遍01背包就好了。
Code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int INF = 0x3f3f3f3f, MAXN = 20005;
int n, m, k, u, v, t[MAXN], w[MAXN], dp[MAXN], father[MAXN];
inline int find(int x) {//并查集
return (x == father[x] ? x : father[x] = find(father[x]));
}
inline void Union(int u, int v) {//合并
int p = find(u), q = find(v);
if (p != q) father[p] = q;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
father[i] = i;
for (int i = 1; i <= k; i++) {
scanf("%d%d", &u, &v);
Union(u, v);//将输入的两个人合并起来
}
for (int i = 1; i <= n; i++)
t[find(i)]++;
int cnt = 0;
for (int i = 1; i <= n; i++)
if (t[i]) w[++cnt] = t[i];//计算价值
for (int i = 1; i <= cnt; i++)
for (int j = m << 1; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);//01背包
int Min = INF, ans = 0;
for (int i = 0; i <= m; i++) {
if (dp[m - i] == m - i) {
printf("%d\n", m - i);
return 0;
}
if (dp[m + i] == m + i) {
printf("%d\n", m + i);
return 0;
}
}
return 0;
}Article Author: XiaoHuang