求助
查看原帖
求助
358174
YyF_Rp_MaxPro楼主2023/4/7 17:05
#include <iostream>

using namespace std;
int n,m,w;
int u[10000];
int v[10000];
int fa[20000];
int f[101];	int d[10001],c[10001];
int find(int x) 
{
	if(fa[x]==x)
	{
		return x;
	}
	return fa[x]=find(fa[x]);
}
int main(){
	cin >> n >> m>> w;
	for(int i = 1;i <=n;i++){
		fa[i]=i;
	} 
	for(int i = 1;i <= n;i++){
		cin >> u[i] >> v[i]; 
	}
	for(int i = 1;i <= m;i++){
		int a,b;
		cin >> a >> b;
		fa[find(a)]=find(b);
	}

	for(int i=1;i<=n;i++)
	{
		if(fa[i]!=i)
		{
			d[find(i)]+=d[i];
			d[i]=0;
			c[find(i)]+=c[i];
			c[i]=0;
		}
	}
	for(int i=1;i<=n;i++) 
	{
	    for(int v=w;v>=c[i];v--)
	    {
	    	f[v]=max(f[v],f[v-c[i]]+d[i]);
		}
	}
	cout << f[w];
}
2023/4/7 17:05
加载中...