就是01背包问题
先用并查集再用01背包
复杂度为nw
代码如下
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> using namespace std; const int maxn=1005; int dp[maxn],w[maxn],b[maxn],f[maxn]; vector<int>group[maxn]; int Find(int x) { if(f[x]==x) return x; return f[x]=Find(f[x]); } void unite(int x,int y) { int xx=Find(x); int yy=Find(y); if(xx!=yy) f[xx]=yy; } int main() { int n,m,W; scanf("%d %d %d",&n,&m,&W); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++) f[i]=i; for(int i=0;i<m;i++){ int x,y; scanf("%d %d",&x,&y); unite(x,y); } for(int i=0;i<maxn;i++) group[i].clear(); for(int i=1;i<=n;i++) group[Find(i)].push_back(i); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { if(Find(i)!=i) continue; for(int j=W;j>=0;j--){ int sumw=0,sumb=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]]); } } if(j>=sumw) dp[j]=max(dp[j],dp[j-sumw]+sumb); } } printf("%d\n",dp[W]); return 0; }