对拍了第一个已解决。
by wtxy2006 @ 2020-06-07 22:17:40
这不是多重背包，而是用并查集来维护每一堆"实力相当的学霸"，然后把它们整体思考后按$01$背包的方式来状态设计以及状态转移，求出选$k$个人时能否满足要求。
by ducati @ 2020-08-03 14:42:21
@[wtxy2006](/user/289573) 无论如何也要%%%
by ducati @ 2020-08-03 14:42:53
@[ducati](/user/87064) 然而我多重背包过了。。。
```
// P2170 选学霸
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define MN 2000005
using namespace std;
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 << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
struct thing {
int v, m;
} things[MN];
int n, m, k;
int fa[MN], g[MN], vis[MN];
int cnt, s[MN], dp[MN], tot;
int find(int x) {
while (x != fa[x]) x = fa[x] = fa[fa[x]];
return fa[x];
}
int main() {
int a, b;
n = read(), m = read(), k = read();
for (int i = 1; i <= n; i++) fa[i] = i, g[i] = 1;
for (int i = 0; i < k; i++) {
a = find(read()), b = find(read());
if (a != b) fa[a] = b, g[b] += g[a];
}
for (int i = 1; i <= n; i++)
if (!vis[find(i)]) vis[find(i)] = 1, s[cnt++] = g[find(i)];
sort(s, s + cnt), a = s[0], b = 1;
for (int i = 1; i <= cnt; i++)
if (a != s[i])
things[tot++] = thing{a, b}, a = s[i], b = 1;
else
b++;
dp[0] = 1;
for (int i = 0; i < tot; i++) {
int now = 1, temp = things[i].m, a = things[i].v;
while (1)
if (temp > now) {
temp -= now;
for (int j = m * 2; j >= now * a; j--)
if (dp[j - now * a]) dp[j] = 1;
now *= 2;
} else {
for (int j = m * 2; j >= temp * a; j--)
if (dp[j - temp * a]) dp[j] = 1;
break;
}
}
for (int i = m, j = m; i >= 0; i--, j++)
if (dp[i]) {
printf("%d", i);
return 0;
} else if (dp[j]) {
printf("%d", j);
return 0;
}
return 0;
}
```cpp
by wtxy2006 @ 2020-08-04 19:18:00
@[ducati](/user/87064) 您莫非认为01背包状态是0和1才叫01背包？
不是一个物体只能选或不选才叫01背包吗？
by wtxy2006 @ 2020-08-04 19:19:54
@[ducati](/user/87064) 但是还要%%%大佬
by wtxy2006 @ 2020-08-04 19:40:20
@[wtxy2006](/user/289573) 对不起，我太菜了，胡扯扰乱您思路了，把我揍扁吧QAQ
by ducati @ 2020-08-04 19:40:25
@[wtxy2006](/user/289573) Orz 懂了，懂了，您的思路与本蒟蒻的不一样%%%%%
by ducati @ 2020-08-04 19:41:01
@[ducati](/user/87064) 没有啦，只是感觉数据如果出刁钻点万一卡成 $O(nm)$ 才用多重背包的。
by wtxy2006 @ 2020-08-04 19:49:01
@[wtxy2006](/user/289573) Orz 本蒟蒻是用$01$背包卡过去的
by ducati @ 2020-08-04 19:50:53