题解 | #B-经商#

思路

01 背包 + 并查集

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int p[N];
int fa[N];
int f[N],v[N],w[N];
int n,m,c;

int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

int main(){
    int T;
    cin>>T;

    while(T--){
        cin>>n>>m>>c;
        for(int i=2;i<=n;i++) cin>>v[i]>>w[i];

        for(int i=1;i<=n;i++) fa[i]=i;
        while(m--){
            int a,b;
            cin>>a>>b;
            a=find(a),b=find(b);
            if(a!=b) fa[a]=b;
        }
        int t=0;
        for(int i=2;i<=n;i++)  if(find(i)==find(1)) p[++t]=i; 
        for(int i=1;i<=t;i++) {
            int pos=p[i];
            for(int j=c;j>=v[pos];j--)   f[j]=max(f[j],f[j-v[pos]]+w[pos]);
        }
        cout<<f[c]<<endl;
        memset(f,0,sizeof f);
    }

    return 0;
}