0pts求条
查看原帖
0pts求条
995215
sunhaozhe111022楼主2024/12/21 15:45
#include<bits/stdc++.h>
using namespace std;
int n,m,f[100005],ans,k,sum=1;
struct data{
	int x,y,z;
}a[100005];
bool cmp(data a,data b)
{
	return a.z<b.z;
}
int find(int a)
{
	return f[a]==a?a:f[a]=find(f[a]);
}
void bing(int a,int b)
{
	f[find(a)]=find(b);
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	f[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].z;
	}
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		if(find(a[i].x)!=find(a[i].y))
		{
			bing(a[i].x,a[i].y);
			sum++;
			ans+=a[i].z;
		}
		if(sum>=n-k)
		{
			cout<<ans;
			return 0;
		}
	}
	cout<<"No Answer";
	return 0;
}
2024/12/21 15:45
加载中...