【题目描述】

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

【输入】

第1行n，m，w，表示n朵云，m个搭配，Joe有w的钱。
第2~n+1行，每行ci，di表示i朵云的价钱和价值。
第n+2~n+1+m行，每行ui，vi，表示买ui就必须买vi，同理，如果买vi就必须买ui。

【输出】

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

【输入样例】

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

【输出样例】

1

#include<iostream>
using namespace std;
int father[10005],c[10005],d[10005];
int mw[10005],f[10005],i,j,n,m,w,x,y;
int find(int x){
    if(father[x]==x) return x;
    return father[x]=find(father[x]);
}
void unite(int x,int y){  //集合归并
    int rx=find(x);
    int ry=find(y);
    if(rx!=ry){
        father[ry]=rx;
        c[rx]+=c[ry];
        d[rx]+=d[ry];
    }
}
int main(){ 
    cin.tie(nullptr);    //实现 scanf 效率------OK
    cin>>n>>m>>w;
    for(i=1;i<=n;++i){
        father[i]=i;
        cin>>c[i]>>d[i];
    }
    for(i=1;i<=m;++i){
        cin>>x>>y;
        unite(x,y);  
    }
    for(i=1;i<=n;++i){ //所有钱可能买多套哦
        x=find(i);
        if(!f[x])f[x]=1; //云朵不可重复
        else continue;
  
        int cx=c[x];
        for(j=w;j>=cx;j--){
            if(mw[j-cx]+d[x]>mw[j])mw[j]=mw[j-cx]+d[x];
        }
    }
    cout<<mw[w];
    return 0;
}//网 pass