并查集专题训练

搭配购买
并查集+01背包；
先合并分块，然后按照01背包模型求解

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 10010;
int p[N], c[N], d[N];
int v[N], w[N];
int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int f[N];
void solve() {
    int n, m, W;
    cin >> n >> m >> W;
    for (int i = 1; i <= n; i++) cin >> c[i] >> d[i], p[i] = i;
    while (m--) {
        int u, v;
        cin >> u >> v;
        if (find(u) == find(v)) continue;
        else {
            c[find(u)] += c[find(v)];
            d[find(u)] += d[find(v)];
            p[find(v)] = find(u);
        }
    }
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
        if (find(i) == i) v[cnt] = c[find(i)], w[cnt] = d[find(i)], cnt++;


    }
    for (int i = 1; i < cnt; i++) {
        for (int j = W; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[W] << endl;




}
int main() {
    solve();

    return 0;
}