lc1252. 搭配购买（并查集 01背包）

Joe觉得云朵很美，决定去山上的商店买一些云朵。
商店里有 nn 朵云，云朵被编号为 1,2,…,n1,2,…,n，并且每朵云都有一个价值。
但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限，所以他希望买的价值越多越好。

输入格式

第 11 行包含三个整数 n，m，wn，m，w，表示有 nn 朵云，mm 个搭配，Joe有 ww 的钱。
第 2∼n+12∼n+1行，每行两个整数 ci，dici，di 表示 ii 朵云的价钱和价值。
第 n+2∼n+1+mn+2∼n+1+m 行，每行两个整数 ui，viui，vi，表示买 uiui 就必须买 vivi，同理，如果买 vivi 就必须买 uiui。

输出格式

一行，表示可以获得的最大价值。

数据范围

1≤n≤100001≤n≤10000,
0≤m≤50000≤m≤5000,
1≤w≤100001≤w≤10000,
1≤ci≤50001≤ci≤5000,
1≤di≤1001≤di≤100,
1≤ui,vi≤n1≤ui,vi≤n

输入样例：

5 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2

输出样例：

1

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, m , vol;
int p[N], v[N], w[N], f[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
//先并查集把连通块绑定，再用01背包做
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 x, y;
        cin >> x >> y;
        int pa = find(x), pb = find(y);
        if (pa != pb) {
            //维护连通块体积和价值
            w[pb] += w[pa];
            v[pb] += v[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;
}