#include <bits/stdc++.h>
using namespace std;
#define maxn 1000
int n,m;
struct edge{
int u,v,w;
}e[maxn];
bool cmp(edge a,edge b){
return a.w<b.w;
}
int ans;
//并查集
int s[maxn];
int find_set(int x){return x==s[x]?x:s[x]=find_set(s[x]);}
void kruskal(){
iota(s,s+n+1,0);//初始化并查集
sort(e,e+m,cmp);//排序
int cnt(0);
for(int i=0;i<m;++i){
int x = find_set(e[i].u);
int y = find_set(e[i].v);
if(x==y) continue;
s[y] = x;
ans+=e[i].w;
if(++cnt == n-1) break;
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;++i){
cin>>e[i].u>>e[i].v>>e[i].w;
}
kruskal();
cout<<ans;
return 0;
}
本文地址：https://blog.csdn.net/weixin_45826022/article/details/109257469
