https://vjudge.csgrandeur.cn/problem/POJ-1287#author=20175101008 题面

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
const int MAXM=2000005;
int n,m,i,j,u,v,total;
struct Edge{
	int start,to;
	int val;
}e[MAXM];
int f[MAXN];
int ans;
int find(int x){
	if (f[x]==x) return x;
	else {
		f[x]=find(f[x]);
		return f[x];
	}
}
bool cmp(Edge a,Edge b){
	return a.val<b.val;
}
void kruskal(){//最小生成树
	//memset(e,0,sizeof(e)); 
	for(int i=1;i<=m;i++){
		u=find(e[i].start);
		v=find(e[i].to);
		if(u==v) continue;//判断在不在同一个并查集里面，在就下一个循环
		ans+=e[i].val;//不在，就加上
		f[u]=v;//连接两个并查集
		total++;
		if(total==n-1) break;//当形成了最小生成树后，退出
	}
}
int main(){
	while(scanf("%d%d",&n,&m)){
		for(i=1;i<=n;i++) f[i]=i;
		for(i=1;i<=m;i++){
			scanf("%d%d%d",&e[i].start,&e[i].to,&e[i].val);
		}
		sort(e+1,e+m+1,cmp);//快排边长
		kruskal();
		printf("%d\n",ans);
		ans=0; 
	}
	return 0;
}

求改