70分求找错
查看原帖
70分求找错
464094
NEO_bone楼主2022/9/16 10:42
#include <cmath>
#include <cstdio>
#define N 10005
#define ll long long
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b

void swap(int &a,int &b)
{
	int c=a+b;
	a=min(a,b);
	b=c-a;
}

int n,w,m;
int c[N];
int d[N];
int fa[N];
int f[N];

int fin(int a)
{
	if(fa[a]==a)
		return a;
	return fa[a]=fin(fa[a]);
}

int main()
{
	scanf("%d%d%d",&n,&m,&w);
	for(int i=1;i<=n;i++)
	{	
		scanf("%d%d",c+i,d+i);
		fa[i]=i;
	}
	while(m--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if(fin(u)>fin(v))
			swap(u,v);
		fa[fin(v)]=fin(u);
	}
	for(int i=1;i<=n;i++)
	{
		if(fa[i]==i)
			continue;
		c[fa[i]]+=c[i];
		c[i]=0;
		d[fa[i]]+=d[i];
		d[i]=0;
	}
	// puts("k\n");
	// for(int i=1;i<=n;i++)
	// 	printf("%d %d %d %d\n",i,fa[i],c[i],d[i]);
	for(int i=1;i<=n;i++)
		for(int l=w;l>=c[i];l--)
			f[l]=max(f[l],f[l-c[i]]+d[i]);
	printf("%d\n",f[w]);
	return 0;
}
2022/9/16 10:42
加载中...