跪求神犇
查看原帖
跪求神犇
940929
huangluochengshuo楼主2024/5/5 19:26
#include<bits/stdc++.h>
using namespace std;
struct bian{
	int u,v,w;
}e[10005];
int n,m,k,cut=0,ans=0,father[10005];
bool comp(bian e1,bian e2){
	return e1.w<e2.w;
}
int getfather(int x){
	if(father[x]==x)	return x;
	father[x]=getfather(father[x]);
	return father[x]; 
}
void merge(int u,int v){
	int a=getfather(u);
	int b=getfather(v);
	if(a!=b)	father[b]=a;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<m;i++)	scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	if(k>n){
		printf("0\n");
		return 0;
	}
	if(k>n){
		printf("No Answer\n");
		return 0;
	}
	sort(e,e+m,comp);
	for(int i=0;i<10005;i++)	father[i]=1;
	for(int i=0;i<m;i++)
		if(getfather(e[i].u)!=getfather(e[i].v)){
			merge(e[i].u ,e[i].v);
			ans+=e[i].w;
			cut++;
			if(n-cut==k)	break;
		}
	if(n-cut==k)	printf("%d\n",ans);
	else	printf("No Answer\n"); 
	return 0;
}
2024/5/5 19:26
加载中...