思路：
最大生成树。
实现：
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 8 struct edge 9 { 10 int a, b, cost; 11 }; 12 edge es[20005]; 13 int ran[1005]; 14 int par[1005]; 15 int n, m, x, y, c; 16 17 void init(int n) 18 { 19 for (int i = 0; i < n; i++) 20 { 21 par[i] = i; 22 ran[i] = 0; 23 } 24 } 25 26 int find(int x) 27 { 28 if (par[x] == x) 29 return x; 30 return par[x] = find(par[x]); 31 } 32 33 void unite(int x, int y) 34 { 35 x = find(x); 36 y = find(y); 37 if (x == y) 38 return; 39 if (ran[x] < ran[y]) 40 { 41 par[x] = y; 42 } 43 else 44 { 45 par[y] = x; 46 if (ran[x] == ran[y]) 47 { 48 ran[x] ++; 49 } 50 } 51 } 52 53 bool same(int x, int y) 54 { 55 return find(x) == find(y); 56 } 57 58 bool cmp(const edge & a, const edge & b) 59 { 60 return a.cost > b.cost; 61 } 62 63 int kru() 64 { 65 init(n); 66 sort(es, es + m, cmp); 67 int res = 0, cnt = 0; 68 for (int i = 0; i < m; i++) 69 { 70 if (!same(es[i].a, es[i].b)) 71 { 72 unite(es[i].a, es[i].b); 73 cnt += 1; 74 res += es[i].cost; 75 } 76 } 77 return cnt < n - 1 ? -1 : res; 78 } 79 80 int main() 81 { 82 scanf("%d %d", &n, &m); 83 for (int i = 0; i < m; i++) 84 { 85 scanf("%d %d %d", &x, &y, &c); 86 es[i].a = x; 87 es[i].b = y; 88 es[i].cost = c; 89 } 90 int tmp = kru(); 91 printf("%d ", tmp); 92 return 0; 93 }