并查集和01背包结合
之前自己写了并查集的思路,但是没有考虑背包选取问题
直接选了钱可以买到的最大集合
事实上有许多钱可以买到的集合组合
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m, vol;
int v[N], w[N];
int p[N];
int f[N];
int ans = 0;
int find(int x) {
if (x != p[x])
p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m >> vol;
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);
int pb = find(b);
if (pa != pb) {//只有这两个点不在同一个集合中才做操作
v[pb] += v[pa];
w[pb] += w[pa];
p[pa] = pb;
}
}
//01 背包问题 将小于价钱的物品可以购买
for (int i = 1; i <= n; i++) {
if (p[i] == i) {
for (int j = vol; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
}
cout << f[vol] << endl;
return 0;
}