整合入根 –> 01背包

#include <iostream>
using namespace std;
const int N = 1E4 + 10;
int w[N], p[N];
int n, m, b;
int parent[N];
int find(int x){
    if(parent[x] == x)  return x;
    return parent[x] = find(parent[x]);
}
int k = 1;
int rw[N], rp[N];
int f[N];
int main(){
    cin >> n >> m >> b;
    for(int i = 1; i <= n; i ++ )   cin >> w[i] >> p[i];
    for(int i = 0; i <= n; i ++ )    parent[i] = i;
    for(int i = 1; i <= m; i ++ ){
        int x, y; cin >> x >> y;
        x = find(x), y = find(y);
        if(x != y){
            parent[x] = y;
        }
    }
    for(int i = 1; i <= n; i ++ ){
        int pi = find(i);
        if(pi == i)    continue;
        w[pi] += w[i];
        p[pi] += p[i];
        w[i] = p[i] = 0;     
    }
    for(int i = 1; i <= n; i ++ ){
        if(w[i] == 0)   continue;
        rw[k] = w[i], rp[k] = p[i];
        k ++ ;
    }
    // 01背包
    for(int i = 1; i < k; i ++ ){
        for(int j = b; j >= rw[i]; j -- ){
            f[j] = max(f[j], f[j - rw[i]] + rp[i]);
        }
    }
    int res = 0;
    for(int i = 0; i <= b; i ++ )   res = max(res, f[i]);
    cout << res << endl;
    return 0;
}

精简版本

#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int w[N], v[N], f[N];
int parent[N];
int find(int t){
    if(parent[t] == t)  return t;
    return parent[t] = find(parent[t]);
}
int main(){
    int n, m, bag;    cin >> n >> m >> bag;
    for(int i = 0; i < N; i ++ )    parent[i] = i;
    for(int i = 1; i <= n; i ++ )    cin >> w[i] >> v[i];
    int a, b;
    while(m -- ){
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if(pa != pb){
            w[pb] += w[pa];
            v[pb] += v[pa];
            parent[pa] = pb; 
        }
    }
    for(int i = 1; i <= n; i ++ ){
        if(parent[i] != i)  continue;    //  只算祖先节点的情况
        for(int j = bag; j >= w[i]; j -- ){
            f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
    }
    cout << f[bag] << endl;
    return 0;
}