90分救助
查看原帖
90分救助
172075
plmplmplm楼主2024/4/8 18:14
#include<bits/stdc++.h>
using namespace std;

int n,m,w;
int a[10005],b[10005],fa[10005],x,y,dp[50005];

int find(int x){
	if(fa[x]==x)return x;
	else{
		fa[x]=find(fa[x]);
		return fa[x];
	}
}

int main(){
  cin>>n>>m>>w;
  for(int i=1;i<=n;i++){
  	cin>>a[i]>>b[i];
  	fa[i]=i;
  }
  for(int i=1;i<=m;i++){
   	cin>>x>>y;
   	int xx,yy;
   	xx=find(x);
   	yy=find(y);
   	fa[xx]=yy;
  }
  for(int i=1;i<=n;i++){
  	if(fa[i]!=i){
  		a[fa[i]]+=a[i];
  		b[fa[i]]+=b[i];
	}
  }
  for(int i=1;i<=n;i++){
  	for(int j=w;j>=a[i];j--){
  		if(fa[i]==i){
  			dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
		  }
	  }
  }
  cout<<dp[w];
   return 0;
}
2024/4/8 18:14
加载中...