60分求助
查看原帖
60分求助
139509
liufukang楼主2021/8/15 09:50
#include<bits/stdc++.h>
using namespace std;
const int maxN=1e5+9;
int n,m,w,pre[maxN],wei[maxN],val[maxN],bag[maxN][1009];
int find(int x){
	int r=x;
	while (r!=pre[r]) r=pre[r];
	while (x!=r){
		int p=pre[x];
		pre[x]=r;
		x=p;
	}
	return r;
}
void join(int x,int y){
	int fx=find(x),fy=find(y);
	if (fx!=fy){
		pre[fx]=fy;
		val[fy]+=val[fx];
		val[fx]=0;
		wei[fy]+=wei[fx];
		wei[fx]=0;
	}
}
int main(){
	cin>>n>>m>>w;
	for (int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		pre[i]=i;
		wei[i]=x;
		val[i]=y;
	}
	for (int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		join(u,v);
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=w;j++){
			if(wei[i]>j) bag[i][j]=bag[i-1][j];
			else bag[i][j]=max(bag[i-1][j-wei[i]]+val[i],bag[i-1][j]);
		}
	}
	cout<<bag[n][w]<<endl;
	return 0;
}

谢谢!

2021/8/15 09:50
加载中...