#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN =
110000;
struct Edge
{
int f, t, d;
}es[MAXN];
int n, m, fa[MAXN];
int find(
int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool cmp(Edge a, Edge b)
{
return a.d < b.d;
}
int main()
{
scanf(
"%d%d", &n, &m);
for(
int i =
1; i <= n; i++)
fa[i] = i;
for(
int i =
1; i <= m; i++)
{
int a, b, c;
scanf(
"%d%d%d", &a, &b, &c);
es[i].f = a;
es[i].t = b;
es[i].d = c;
}
sort(es +
1, es +
1 + m, cmp);
long long ans =
0;
for(
int i =
1; i <= m; i++)
{
int x = find(es[i].f);
int y = find(es[i].t);
if(x != y)
{
ans += es[i].d;
fa[x] = y;
}
}
printf(
"%lld", ans);
return 0;
}
转载于:https://www.cnblogs.com/Loi-Vampire/p/6017068.html
相关资源：JAVA上百实例源码以及开源项目
