70pts求助
查看原帖
70pts求助
996200
President_Zhao楼主2024/7/16 16:52

样例没有通过,#2#3#4#11WA,希望大佬帮助,悬关

#include<bits/stdc++.h>
using namespace std;
struct my
{
	int w;
	int cost;
}cloud[10010];
int coldteagroup[10010];
int dp[100010];
#define cl cloud
#define ctg coldteagroup
int find(int a)
{
	if(ctg[a]==a)
	{
		return a;
	}
	else
	{
		return ctg[a]=find(ctg[a]);
	}
}
int main()
{
	int n,m,w;
	cin>>n>>m>>w;
	for(int i=1;i<=n;i++)
	{
		cin>>cl[i].cost>>cl[i].w;
		ctg[i]=i;
	}
	for(int j=1;j<=m;j++)
	{
		int a,b;
		cin>>a>>b;
		if(a>b)
		{
			ctg[a]=b;
		}
		else
		{
			ctg[b]=a;
		}
	}
	for(int j=1;j<=n;j++)
	{
		if(find(j)!=j)
		{
			cl[find(j)].cost+=cl[j].cost;
			cl[find(j)].w+=cl[j].w;
			cl[j].cost=-1;
		}
	}
	for(int j=1;j<=n;j++)
	{
		if(cl[j].cost!=-1)
			for(int i=w;i>=cl[j].cost;i--)
			{
				dp[i]=max(dp[i],dp[i-cl[j].cost]+cl[j].w);
			}
	}int ans=-1;
	for(int j=1;j<=n;j++)
	{
		ans=max(ans,dp[j]);
	}
	cout<<ans;
}
2024/7/16 16:52
加载中...