#include<bits/stdc++.h>using namespace std;int n,m,w,f[10005],money[10005],v[10005],ans(0),dp[10005],used[10005],k(0);int ww[10005],mm[10005];int find(int x){ if(f[x]==x)return x; return find(f[x]);}void UN(int x,int y){ int a=find(x); int b=find(y); f[a]=b; money[b]+=money[a]; v[b]+=v[a];}int main(){ scanf("%d%d%d",&n,&m,&w); for(int i=1;i<=n;i++) scanf("%d %d",&money[i],&v[i]); for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=m;i++) { int ll,kk; scanf("%d%d",&ll,&kk); UN(ll,kk); } for(int i=1;i<=n;i++) { int a=find(i); if(a==i) { k++; ww[k]=money[i]; mm[k]=v[i]; } } for(int i=1;i<=k;i++) { for(int j=w;j>=ww[i];j--) { dp[j]=max(dp[j],dp[j-ww[i]]+mm[i]); } } cout<<*max_element(dp+1,dp+1+w); return 0;}
转载于:https://www.cnblogs.com/647Z/p/7363059.html
相关资源：JAVA上百实例源码以及开源项目