并查集+背包 【CF741B】 Arpa's weak amphitheater and Mehr
发布时间:2020-12-14 04:16:22 所属栏目:大数据 来源:网络整理
导读:Descirption 有n个人,每个人都有颜值bi与体重wi。剧场的容量为W。有m条关系,xi与yi表示xi和yi是好朋友,在一个小组。 每个小组要么全部参加舞会,要么参加人数不能超过1人。 问保证总重量不超过W,剧场中的颜值最大能到多少? Input 第一行,三个整数n,m,w
不错的一个题。 考察:并查集+分组背包。 我们先并查集将在一组的人处理出来. 顺便处理一下每个组的编号与组中每个人是谁. (belong[x])则代表(x)组的编号。 我们用(ins[i][j])代表第(i)组的第(j)个元素是谁。 然后每一个小组可以全部去,可以去一个,可以不去。 考虑问题转化,我们将这一个小组看成一个物品,直接把其价值及体积加入到当前组即可。 处理完之后,跑分组背包即可。 需要注意的一点是:如果某一组只有一个元素,我们不能再将其看为一个物品重新加入(克隆?)
#include<cstdio> #include<iostream> #include<algorithm> #define R register using namespace std; const int gz=1008; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int n,w,wi[gz],f[gz],b[gz],dp[gz]; int find(R int x){return f[x]==x?x:f[x]=find(f[x]);} int belong[gz],cnt; int ins[gz][gz],W[gz],B[gz]; int main() { in(n),in(m),in(w); for(R int i=1;i<=n;i++)in(wi[i]); for(R int i=1;i<=n;i++)in(b[i]); for(R int i=1;i<=n;i++)f[i]=i; for(R int i=1,x,y;i<=m;i++) { in(x),in(y); R int fa=find(x); R int fb=find(y); if(fa==fb)continue; f[fa]=fb; } for(R int i=1;i<=n;i++) { R int x=find(i); if(!belong[x])belong[x]=++cnt; ins[belong[x]][++ins[belong[x]][0]]=i; W[belong[x]]+=wi[i]; B[belong[x]]+=b[i]; } for(R int i=1;i<=cnt;i++) { if(ins[i][0]!=1) { ins[i][++ins[i][0]]=n+1; wi[n+1]=W[i]; b[n+1]=B[i]; } for(R int j=w;j>=0;j--) for(R int k=1;k<=ins[i][0];k++) if(j>=wi[ins[i][k]]) dp[j]=max(dp[j],dp[j-wi[ins[i][k]]]+b[ins[i][k]]); } printf("%d",dp[w]); } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |