题目链接

经商

题目思路

并查集构图，再用01背包解决

代码实现

#include<bits/stdc++.h>
using namespace std;
const int Max=1e6;
int n,m,c;
int fa[Max],dp[Max],cost[Max],value[Max];
void init()
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int find(int x)
{
    if(fa[x]!=x)
    {
        fa[x]=find(fa[x]);
    }
    return fa[x];
}
void merge(int x,int y)
{
    int fx=find(x),fy=find(y);
    fa[find(x)]=fy;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {

        cin>>n>>m>>c;
        init();
        for(int i=2;i<=n;i++)
        {
            cin>>cost[i]>>value[i];
        }
        for(int i=1;i<=m;i++)
        {
            int u,v;
            cin>>u>>v;
            merge(u,v);
        }
        memset(dp,0,sizeof dp);
        for(int i=2;i<=n;i++)
        {
            if(find(i)==find(1))
            {
                for(int j=c;j>=cost[i];j--)
                    dp[j]=max(dp[j],dp[j-cost[i]]+value[i]);
            }
        }
        cout<<dp[c]<<endl;
    }
}