求助克鲁斯卡尔!!!
查看原帖
求助克鲁斯卡尔!!!
418419
ko_no_lzx_da楼主2022/3/28 13:11
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const long long N=10000000;
long long cnt;
long long n,m;
long long ans;
long long fa[N];
long long head[N];
struct node{
	long long from,to,v,next;
}edge[N];
void add(long long from,long long to,long long v){
	edge[++cnt].to=to;
	edge[cnt].from=from;
	edge[cnt].v=v;
}
bool cmp(node a,node b){
	return a.v<b.v;
}        
long long find(long long x){
	if(fa[x]!=x){
		return fa[x]=find(fa[x]);
	}else{
		return x;
	}
}
void with(long long x,long long y){
	if(fa[x]!=x)fa[y]=fa[find(x)];
	else fa[y]=fa[x];
}
int main(){
	cin >>n>>m;
	for(long long i=1;i<=n;i++)fa[i]=i;
	for(long long i=1;i<=m;i++){
		long long f,t,v;
		cin >>f>>t>>v;
		add(f,t,v);
		add(t,f,v);
	}
	long long num=0;
	sort(edge+1,edge+1+m,cmp);
	for(long long i=1;i<=m;i++){
		long long x=edge[i].from,y=edge[i].to;
		if(find(x)!=find(y)){
			with(x,y);
			ans+=edge[i].v;
			num++;
		}
		if(num==n-1){
			cout <<ans;
			return 0;
		}
	}
	cout <<"orz";
	return 0;	
}



2022/3/28 13:11
加载中...