原题
没有搭配就是一道裸01背包，搭配的话用并查集并一并，结束后只取他们的祖先加入背包计算。
#include<iomanip> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,mon,v[10001],w[10001],fa[10001],f[10001]; int find(int x) { if(fa[x]==x) return x; else return fa[x]=find(fa[x]); } int main() { cin>>n>>m>>mon; for(int i=1;i<=n;++i) fa[i]=i; for(int i=1;i<=n;++i) cin>>w[i]>>v[i]; for(int i=1;i<=m;++i) { int a,b;cin>>a>>b; if(find(a)==find(b)) continue; v[find(b)]+=v[find(a)]; w[find(b)]+=w[find(a)]; fa[find(a)]=find(b); } for(int i=1;i<=n;++i) for(int j=mon;j>=w[i];--j) { if(i!=fa[i]) continue; f[j]=max(f[j],f[j-w[i]]+v[i]); } cout<<f[mon]; return 0; }
