搭配购买（并查集+0/1背包）

Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n朵云，云朵被编号为1,2,…,n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。但是Joe的钱有限，所以他希望买的价值越多越好。
输入
第1行n(<=10000)、m(>=5000)、w(<=10000)，表示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

并查集直接维护就好了

每次merge的时候把花费和价值也叠加给那一个

最后把所有自己是自己father的拿出来做一个0/1背包就好了

结果一维数组忘了价值要倒序枚举

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();
    int res=0;
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return res;
}
int n,m,we,fa[10005],w[10005],c[10005],dp[10005];
inline int find(int x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
inline void merge(int x,int y){
    int f1=find(x),f2=find(y);
    if(f1!=f2)fa[f1]=f2,c[f2]+=c[f1],w[f2]+=w[f1];
}
int main(){
    n=read(),m=read(),we=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++){
        c[i]=read(),w[i]=read();
    }
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        merge(u,v);
    }
    for(int i=1;i<=n;i++){
        if(fa[i]==i){
            for(int j=we;j>=c[i];j--){
                dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
            }
        }
    }
    cout<<dp[we]<<'
';
}