思路：
最大生成树。
实现：
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std; struct edge
{
int a, b, cost;
};
edge es[];
int ran[];
int par[];
int n, m, x, y, c; void init(int n)
{
for (int i = ; i < n; i++)
{
par[i] = i;
ran[i] = ;
}
} int find(int x)
{
if (par[x] == x)
return x;
return par[x] = find(par[x]);
} void unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y)
return;
if (ran[x] < ran[y])
{
par[x] = y;
}
else
{
par[y] = x;
if (ran[x] == ran[y])
{
ran[x] ++;
}
}
} bool same(int x, int y)
{
return find(x) == find(y);
} bool cmp(const edge & a, const edge & b)
{
return a.cost > b.cost;
} int kru()
{
init(n);
sort(es, es + m, cmp);
int res = , cnt = ;
for (int i = ; i < m; i++)
{
if (!same(es[i].a, es[i].b))
{
unite(es[i].a, es[i].b);
cnt += ;
res += es[i].cost;
}
}
return cnt < n - ? - : res;
} int main()
{
scanf("%d %d", &n, &m);
for (int i = ; i < m; i++)
{
scanf("%d %d %d", &x, &y, &c);
es[i].a = x;
es[i].b = y;
es[i].cost = c;
}
int tmp = kru();
printf("%d\n", tmp);
return ;
}