POJ - 1287最小生成树 krusal

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int fa[1000]; struct edge { int come, to, cost; }d[3000]; bool cmp(edge p1, edge p2) { return p1.cost < p2.cost; } int getf(int x) { if(x == fa[x]) return x; return fa[x] = getf(fa[x]); } void init() { for(int i = 0; i < 1000; i++) fa[i] = i; } void Union(int x, int y) { x = getf(x); y = getf(y); if(x == y) return; fa[x] = y; } bool same(int x, int y) { if(getf(x) == getf(y)) return 0; return 1; } int main() { int m, n; while(scanf("%d%d", &n, &m) == 2) { int sum = 0; init(); for(int i = 0; i < m; i++) cin >> d[i].come >> d[i].to >> d[i].cost; sort(d, d + m, cmp); for(int i = 0; i < m; i++) { if(same(d[i].come, d[i].to)) { Union(d[i].come, d[i].to); sum += d[i].cost; } } cout << sum << endl; } return 0; }