此题我大概翻译一下就是在01背包的基础上加了一些限制条件,题目多次将给出的A,B物品两件捆绑起来:只要装了A就必须装上B。我的思路是用并查集再加普通背包。但wa了一个点。。。
#include <bits/stdc++.h>
#define int long long
#define maxm 10000005
#define maxn 1005
using namespace std;
int n,m,cnt,W,x,y,fa[maxm],f[maxm];
struct node{
int w,v;
}a[maxm],b[maxm];
string s;
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
}
}
int getfa(int u){
if(fa[u]==u)return u;
return fa[u]=getfa(fa[u]);;
}
signed main(){
cin>>n>>m>>W;
init();
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].v;
}
for(int i=1;i<=m;i++){
cin>>x>>y;
if(getfa(x)==getfa(y))continue;
else{
a[getfa(x)].w+=a[getfa(y)].w;
a[getfa(x)].v+=a[getfa(y)].v;
a[getfa(y)].w=a[getfa(y)].v=0;
fa[y]=fa[x];
}
}
for(int i=1;i<=n;i++){
for(int j=W;j>=a[i].w;j--){
f[j]=max(f[j],f[j-a[i].w]+a[i].v);
}
}
cout<<f[W];
return 0;
}