90pts玄关求助 码风良好
查看原帖
90pts玄关求助 码风良好
1108111
XYY62012楼主2024/11/22 17:29
#include<bits/stdc++.h>
using namespace std;
const int MAXN=595950;
int n,m,k;
int cnt,ans;
int father[MAXN];
struct Edge{//定义结构体
	int a;//起点
	int b;//终点
	int w;//边权
}f[MAXN];
bool cmp(Edge a,Edge b){//sort排序规则,按费用从低到高排序
	return a.w<b.w;
}
int fath(int x){
	if(father[x]!=x) father[x]=fath(father[x]);
	return father[x];
}
void unionn(int x,int y){
	int fa=fath(x);
	int fb=fath(y);
	if(fa!=fb) father[fa]=fb;
}
int main(){
	cin>>n>>m>>k;//点的个数,边的数量,要连多少条边
	for(int i=1;i<=n;i++){
		father[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>f[i].a>>f[i].b>>f[i].w;
	}
	sort(f,f+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(fath(f[i].a)!=fath(f[i].b)){
			unionn(f[i].a,f[i].b);
			ans+=f[i].w;
			cnt++;
		}
		if(cnt>=n-k){
			break;
		}
	}
	if(cnt>=n-k){
		cout<<ans<<endl;
	}else{
		cout<<"No Answer"<<endl;
	}
	return 0;
}
2024/11/22 17:29
加载中...