点击打开链接
题意：有n个人，每个人都有颜值bi与体重wi。剧场的容量为W。有m条关系，xi与yi表示xi和yi是好朋友，在一个小组。 每个小组要么全部参加舞会，要么参加人数不能超过1人。 问保证总重量不超过W，剧场中的颜值最大能到多少？
先用并查集分组,然后在每组进行01背包即可
#include <iostream> #include <algorithm> #include <map> #include <vector> #include <cstring> using namespace std; typedef long long ll; const int N=1e3+20; ll fa[N],n,b[N],w[N],W; ll dp[N];//dp[i][j] 前i组 体重为j时的最大beauty // dp[i][j]=max(dp[i-1][j],max(dp[i-1][j-tot[i]]+bea[i],dp[i-1][j-w[k]]+b[k])) vector<int> group[N]; int find(int x) { if(fa[x]!=x) { fa[x]=find(fa[x]); } return fa[x]; } void Union(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) { fa[fx]=fy; } } void calc() { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { if(i!=find(i)) continue;//每组进行一次决策 for(int j=W;j>=0;j--) { ll sumb=0,sumw=0; for(int k=0;k<group[i].size();k++)//只选一个 { sumw+=w[group[i][k]]; sumb+=b[group[i][k]]; if(j>=w[group[i][k]]) { dp[j]=max(dp[j],dp[j-w[group[i][k]]]+b[group[i][k]]); } //cout<<i<<' '<<j<<" "<<dp[j]<<endl; } if(j>=sumw) { dp[j]=max(dp[j],dp[j-sumw]+sumb); } } } cout<<dp[W]<<endl; } int main() { int m; cin>>n>>m>>W; for(int i=1;i<=n;i++) { cin>>w[i]; fa[i]=i; } for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; Union(x,y); } for(int i=1;i<=n;i++)//分组 { group[find(i)].push_back(i);//每组进行一次决策 } calc(); return 0; }
