目录
- $code$
题目
思路
并查集+01背包,用并查集将捆绑在一起购买的价格和价值都转移到一个上去,然后做一遍01背包。
$code$
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> #define maxn 10001 using namespace std; int n,m,k; int c[maxn],w[maxn],fa[maxn],f[maxn<<1]; int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); } inline void read(int &t){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} t=f?-x:x; } int main(){ read(n),read(m),read(k); for(int i=1;i<=n;++i){ fa[i]=i; read(c[i]),read(w[i]); } for(int i=1,x,y;i<=m;++i){ read(x),read(y); if(find(x)!=find(y)) fa[find(x)]=find(y); } for(int i=1;i<=n;++i){ if(find(i)!=i){ w[find(i)]+=w[i]; c[find(i)]+=c[i]; w[i]=0,c[i]=0; } } for(int i=1;i<=n;++i){ if(w[i]==0&&c[i]==0) continue; for(int j=k;j>=c[i];--j){ f[j]=max(f[j],f[j-c[i]]+w[i]); } } printf("%d\n",f[k]); return 0; }