并查集+01背包80分,求助大佬
查看原帖
并查集+01背包80分,求助大佬
529679
involutionKing楼主2023/3/2 21:11

蒟蒻代码求帮助

/*[in]
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
[out]
1
*/
#include<bits/stdc++.h>
#define maxn 10005
using namespace std;
int n, m, w, i, j, c[maxn], d[maxn], f[maxn], dp[maxn];
int find(int x){
	if(f[x]!=x){
		f[x] = find(f[x]);
	}
	return f[x];
} 
void add(int rr1, int rr2){
	int r1 = find(rr1);
	int r2 = find(rr2);
	if(r1!=r2){
		f[r1] = r2;
	}
}
int main(){
	cin>>n>>m>>w;
	for(i=1;i<=n;i++){
		cin>>c[i]>>d[i];
		f[i] = i;
	}
	for(i=1;i<=m;i++){
		int u, v;
		cin>>u>>v;
		c[v] += c[u];
		d[v] += d[u];
		add(u, v);
	}
	for(i=1;i<=n;i++){
		// f[i]!=i意思是这件商品不存在 
		if(f[i]!=i){
			continue;
		}
		cout<<"i="<<i<<"  价格:"<<c[i]<<"  价值:"<<d[i]<<endl;
		for(j=w;j>=c[i];j--){
			if(dp[j-c[i]]+d[i] > dp[j]){
				dp[j] = dp[j-c[i]]+d[i];
			}
		}
	}
	cout<<dp[n];
	return 0;
}

2023/3/2 21:11
加载中...