【并查集】搭配购买
原题链接
并查集+01背包。先将需要搭配购买的云用并查集绑定，再利用01背包求出价值的最大值。
代码实现：
#include
#define N 10000+10
using namespace std;
int n,m,w;
int c[N],d[N];
int u,v;
int fa[N];
int vv[N],ww[N];
int f[N];
int get(int x){
if(x==fa[x])return x;
return fa[x]=get(fa[x]);
}
void merge(int a,int b){
fa[get(a)]=get(b);
}
int main(){
cin>>n>>m>>w;
memset(vv,0,sizeof vv);
memset(ww,0,sizeof ww);
for(int i=1;i>c[i]>>d[i];
fa[i]=i;
}
for(int i=1;i>u>>v;
merge(u,v);
}
int cnt=0;
for(int i=1;i<=n;i++){
int ff;ff=get(i);
vv[ff]+=c[i];
ww[ff]+=d[i];
}
for(int i=1;i=vv[i];j--)
f[j]=max(f[j],f[j-vv[i]]+ww[i]);
cout<<f[w];
return 0;
}
ZYzyZzzz
原创文章 22获赞 24访问量 964
关注
私信
展开阅读全文
作者：ZYzyZzzz
