http://wikioi.com/problem/1231/
Kruskal+并查集。comp函数里面如果用const引用的话，可以减少copy。并查集find的时候是递归找父亲的根。无他。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
#define MAX(a, b) a>b?a:b
#define LEN 100005
using namespace std; struct Edge {
int a;
int b;
int val;
}; int n, m;
Edge edges[LEN];
int father[LEN]; int find(int x) {
if (father[x] != x)
father[x] = find(father[x]);
return father[x];
} void merge(int x, int y) {
father[find(x)] = find(y);
} void init() {
memset(father, 0, sizeof(father));
memset(edges, 0, sizeof(edges));
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].val);
}
for (int i = 1; i <= n; i++) {
father[i] = i;
}
} bool comp(const Edge &a, const Edge &b) {
return a.val < b.val;
} int main()
{
init();
sort(edges, edges+m, comp);
long long sum = 0;
for (int i = 0; i < m; i++) {
int x = edges[i].a;
int y = edges[i].b;
if (find(x) != find(y)) {
sum += edges[i].val;
merge(x, y);
}
}
printf("%lld\n", sum);
return 0;
}