经商

很久很久没写题解了，哈哈哈哈哈哈
核心算法并查集，01背包问题
刚开始做的时候我没看过01背包，只好去现学01背包问题。
题意：
商人，自古都是利益为先，所以本题中的商人自然想赚的更多，但是呢商人和不认识的人又不能进行交涉（可能比较害羞吧），只能和认识的人或者<认识的人>认识的人...交流，这时候应该很容易联想到并查集，让能交流的人都在同一个集合中。
首先是并查集的find（x）；用于查找是否在同一个集合

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);//三目运算符真的很香
}

然后合并：

void merge(int x,int y){
    fa[find(x)]=find(y);
}

并查集之后呢就是一个单纯的01背包问题，不过需要考虑的只有与老板在同一个集合中的元素；
所以需要在dp中加上一个条件；

    if(find(i)==find(1))

只有满足这个条件的人才能被老板利用（利用会不会太阴险，管他呢，哈哈哈哈）
贴上ac代码

#include<iostream>
#include<string.h>
using namespace std;
#define N 1000000
int dp[N];
int fa[N];
struct node{
    int pay;
    int get;
} peaple[100000];//我用的结构体存一个用户的花费与价值，其实可以分成两个数组存的；
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
int main(){
    int T;
    cin>>T;
    while(T--){
        int m,n,c;
        cin>>n>>m>>c;
        for(int i=1;i<=n;i++)fa[i]=i;
        for(int i=2;i<=n;i++){
            cin>>peaple[i].pay>>peaple[i].get;
        }
        int x,y; 
        for(int i=1;i<=m;i++){
        cin>>x>>y;
        merge(x,y); 
        } 
        memset(dp, 0, sizeof(dp));//T组输入记得初始化
        for(int i=2;i<=n;i++){
            if(find(i)==find(1)){
                for(int j=c;j>=peaple[i].pay;j--){
                    dp[j]=max(dp[j],dp[j-peaple[i].pay]+peaple[i].get);
                }
            }
        }
        cout<<dp[c]<<endl;
    }
    return 0;
}