a和b合并时要判祖先不同，不然会重复合并
by yukimainyan @ 2024-02-02 09:14:13
@[xq_z](/user/611614)
```cpp
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int fa[10005], n, m, w, dp[10005], c[10005], d[10005], u[10005], v[10005], price[10005], jj[10005];
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int f1 = find(x), f2 = find(y);
if (f1 != f2) {
fa[f1] = f2;
}
}
signed main() {
cin >> n >> m >> w;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= n; i++) {
cin >> c[i] >> d[i];
}
for (int i = 1; i <= m; i++) {
cin >> u[i] >> v[i];
merge(u[i], v[i]);
merge(v[i], u[i]);
}
for (int i = 1; i <= n; i++) {
price[find(i)] += c[i];
jj[find(i)] += d[i];
}
for (int i = 1; i <= n; i++) {
for (int j = w; j >= price[i]; j--) {
dp[j] = max(dp[j], dp[j - price[i]] + jj[i]);
}
}
cout << dp[w];
}
```
by int_stl @ 2024-02-06 09:00:32