MST求助
查看原帖
MST求助
267517
Mikemao666楼主2020/10/1 13:45
#include<bits/stdc++.h>
using namespace std;
struct node{
	int u,v,w;
}edge[10001];
int f[1001],tot,cnt;
bool cmp(node a,node b){
	return a.w<b.w;
}int find(int x){
	if(x==f[x])return x;
	else return f[x]=find(f[x]);
}int n,m,k;
void MST(){
	for(int i=1;i<=n;++i){
		int u=find(edge[i].u),v=find(edge[i].v);
		if(u==v)continue;
		tot+=edge[i].w;
		f[v]=u;
		if(++cnt==k-1){
			printf("%d",tot);
			return;
		}
	}puts("No Answer");
}

int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;++i){
		f[i]=i;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
	}sort(edge+1,edge+m+1,cmp); 
	MST();
	return 0;
} 

Rt

2020/10/1 13:45
加载中...