问一道背包
  • 板块题目总版
  • 楼主Enoch006
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/6/14 13:57
  • 上次更新2023/10/23 13:10:22
查看原帖
问一道背包
538683
Enoch006楼主2023/6/14 13:57

此题我大概翻译一下就是在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;
}
2023/6/14 13:57
加载中...