1 //并查集+01背包 2 //用并查集把几件物品合为一件 3 #include<bits/stdc++.h> 4 using namespace std; 5 const int maxn=10005; 6 const int maxv=10005; 7 int n,m,v_tot,tot,v[maxn],w[maxn],dp[maxv]; 8 struct node{ 9 int fa,cnt,v_sum,w_sum; 10 }f[maxn]; 11 int find(int x) 12 { 13 if(f[x].fa==x) return x; 14 return f[x].fa=find(f[x].fa); 15 } 16 void Union(int x,int y)//合并时把体积和价值也合并 17 { 18 int fax=find(x),fay=find(y); 19 if(fax==fay) return; 20 if(f[fax].cnt<=f[fay].cnt) {f[fax].fa=fay;f[fay].cnt+=f[fax].cnt;f[fay].v_sum+=f[fax].v_sum;f[fay].w_sum+=f[fax].w_sum;} 21 else {f[fay].fa=fax;f[fax].cnt+=f[fay].cnt;f[fax].v_sum+=f[fay].v_sum;f[fax].w_sum+=f[fay].w_sum;} 22 find(x),find(y);//合并完需要再路径压缩 23 } 24 void init()//并查集初始化 25 { 26 for(int i=1;i<=n;++i) 27 f[i].fa=i,f[i].cnt=1, 28 f[i].v_sum=v[i],f[i].w_sum=w[i]; 29 } 30 int main() 31 { 32 scanf("%d%d%d",&n,&m,&v_tot); 33 for(int i=1;i<=n;++i) scanf("%d%d",&v[i],&w[i]); 34 init(); 35 for(int i=1,x,y;i<=m;++i) scanf("%d%d",&x,&y),Union(x,y); 36 for(int i=1;i<=n;++i) 37 if(find(i)==i) v[++tot]=f[i].v_sum,w[tot]=f[i].w_sum; 38 for(int i=1;i<=tot;++i) 39 for(int j=v_tot;j>=v[i];--j) 40 dp[j]=max(dp[j],dp[j-v[i]]+w[i]); 41 printf("%d",dp[v_tot]); 42 return 0; 43 }