并查集+01背包
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N = 1e4+10; int fa[N],value[N],cost[N],dp[N]; int n,m,w; set<PII> s; int find(int x) { if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x]; } int main() { for(int i=0;i<N;i++) fa[i]=i; cin>>n>>m>>w; for(int i=1;i<=n;i++) cin>>cost[i]>>value[i]; int a,b; for(int i=0;i<m;i++) { cin>>a>>b; int faa=find(a),fbb=find(b); if(faa!=fbb) { fa[faa]=fbb; cost[fbb]+=cost[faa]; value[fbb]+=value[faa]; } } //01背包默写 for(int i=1;i<=n;i++) { if(fa[i]==i) { for(int j=w;j>=cost[i];j--) { dp[j]=max(dp[j],dp[j-cost[i]]+value[i]); } } } cout<<dp[w]; return 0; }