玄关

P1455

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[110000],f[110000],n,m,w,w1[110000],v[110000],sum[110000],sum1[110000];
int find(int x){
    if(f[x]==x)return x;
    return f[x]=find(f[x]);
}
int main(){
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=1;i<=n;i++){
        cin>>w1[i]>>v[i];
        sum[i]=w1[i];
        sum1[i]=v[i];
    }
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        x=find(x);
        y=find(y);
        if(x!=y){
            f[x]=y;
            sum[y]+=sum[x];
            sum1[y]+=sum1[x];
        }
    }
    for(int i=1;i<=n;i++){
        int x=find(i);
        for(int j=w;j>=w1[x];j--){
           if(j-sum[x]>=0) dp[j]=max(dp[j],dp[j-sum[x]]+sum1[x]);
           else continue;
        }
    }
    cout<<dp[w];
    return 0;
}

90分求调