AcWing 1252. 搭配购买
原题链接
简单
作者:
松鼠爱葡萄
,
2020-10-17 10:38:14
,
所有人可见
,
阅读 639
#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int n, m, vol;
int p[N], v[N], w[N], f[N];
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];
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
int pa = find(a), pb = find(b);
if (pa != pb) {
w[pb] += w[pa];
v[pb] += v[pa];
p[pa] = p[pb];
}
}
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;
}