思路
0-1背包加并查集
这种联通关系显然是用并查集做。
捆绑关系,集合内部所有总体积、总价值维护到根节点。需要注意的是:
体积、价值维护到根节点之后,赋值根节点不能反了。
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int n, m, ww;
int v[N], w[N];
int f[N];
int p[N];
int find(int x)
{
if (p[x] == x) return x;
else return p[x] = find(p[x]);
}
int main()
{
cin >> n >> m >> ww;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
while (m--)
{
int a, b;
cin >> a >> b;
int pa = find(a), pb = find(b);
if (pa != pb)
{
v[pa] += v[pb];
w[pa] += w[pb];
p[pb] = pa;
}
}
for (int i = 1; i <= n; i++)
if (p[i] == i)
for (int j = ww; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[ww];
return 0;
}