50分求助
查看原帖
50分求助
752977
yuzhongbutong123楼主2023/12/15 21:41
#include<bits/stdc++.h>
using namespace std;

const int N=100010;

struct Node 
{
	int x,y,l;
}ling[N];

int n,m,k,ans;

int fa[N],v[N];

bool cmp(Node a,Node b)
{
	return a.l<b.l;
}

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

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	if(n-m>k)
	{
		printf("No Answer\n");
		return 0; 
	} 
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&ling[i].x,&ling[i].y,&ling[i].l);
	}
	int maxn=-1;
	sort(ling+1,ling+1+m,cmp);
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int xx=cha(ling[i].x);
		int yy=cha(ling[i].y);
		if(xx==yy)
		{
			continue;
		}
		fa[xx]=yy;
		v[xx]=ling[i].l;
		ans+=ling[i].l;
	}
	int tot=0,sum=0;
	for(int i=1;i<=n;i++)
	{
		if(v[i]==0)
		{
			sum++;
		}
	}
	while(tot<k-sum)
	{
		int maxn=-1,t=0;
		for(int i=1;i<=n;i++)
		{
			if(maxn<v[i])
			{
				maxn=v[i];
				t=i;
			}
		}
		v[t]=0;
		ans-=maxn;
		tot++;
	}
	printf("%d",ans);
	return 0;
}
2023/12/15 21:41
加载中...