10分求助
查看原帖
10分求助
1045845
dyf1013楼主2024/8/17 20:09
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
const int M=200010;
const int INF=0x3f3f3f3f;
int n,m,k;
int p[N];
struct Edge{
	int a,b,w;
}edges[M];
bool operator<(Edge x,Edge y){
	return x.w<y.w;
}
int find(int x)
{
	if(p[x]!=x)
		p[x]=find(p[x]);
	return p[x];
}
int kruskal()
{
	int cnt=0;
	int MST=0;
	sort(edges,edges+m);
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=0;i<m;i++)
	{
		int a=edges[i].a;
		int b=edges[i].b;
		int w=edges[i].w;
		a=find(a);
		b=find(b);
		if(a!=b)
		{
			p[a]=b;
			MST+=w;
			cnt++;
		}
	}
	if(cnt<n-k) return INF;
	else return MST;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<m;i++)
	{
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		edges[i]={a,b,w};
	}
	int res=kruskal();
	if(res==INF) printf("No Answer");
	else printf("%d",res);
	return 0;
} 
2024/8/17 20:09
加载中...