WA10求助
查看原帖
WA10求助
794148
cyx20091026楼主2024/12/14 08:24
#include<bits/stdc++.h>
using namespace std;
int n,m,w;
int ci[100001],di[100001];
int dp[100001];
int fa[100001];
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
	cin>>n>>m>>w;
	for(int i=1;i<=n;i++){
		cin>>ci[i]>>di[i];
		fa[i]=i;
	}
	int a,b;
	for(int i=1;i<=m;i++){		
		cin>>a>>b;
		int eu=find(a);
		int ev=find(b);
		fa[eu]=ev;
	}
	for(int i=1;i<=n;i++){
		int ex=find(i);
		if(ex!=i){
			di[ex]+=di[i];
			ci[ex]+=ci[i];
			di[i]=0;
			ci[i]=0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=w;j>=di[i];j--){
			dp[j]=max(dp[j],dp[j-ci[i]]+di[i]);
		}
	}
	cout<<dp[w];
	return 0;
} 
2024/12/14 08:24
加载中...