1 /* 2 最小生成树之kruskal算法--并查集(数据结构)实现 3 建立一个结构体,记录两点和它们的距离,依照距离升序排序 4 不连通就累加距离,即为最小生成树的长度 5 */ 6 #include7 #include 8 #include 9 #include 10 using namespace std;11 12 const int MAXN = 5e3 + 10;13 const int INF = 0x3f3f3f3f;14 int rt[MAXN];15 struct Node16 {17 int u, v, w;18 }node[MAXN];19 20 bool cmp(Node x, Node y) { return x.w < y.w;}21 22 int Find(int x) { return (rt[x] == -1) ? x : rt[x] = Find (rt[x]);}23 24 void Union(int x, int y)25 {26 x = Find (x); y = Find (y);27 if (x > y) rt[y] = x;28 else if (x < y) rt[x] = y;29 }30 31 bool same(int x, int y) { return (Find (x) == Find (y));}32 33 int main(void) //HDOJ 1233 还是畅通工程34 {35 //freopen ("inB.txt", "r", stdin);36 int n, m;37 38 while (~scanf ("%d", &n) && n)39 {40 m = n * (n - 1) / 2;41 memset (rt, -1, sizeof (rt));42 for (int i=1; i<=m; ++i)43 {44 scanf ("%d%d%d", &node[i].u, &node[i].v, &node[i].w);45 }46 sort (node+1, node+1+m, cmp);47 int sum = 0;48 for (int i=1; i<=m; ++i)49 {50 int x = node[i].u; int y = node[i].v;51 int w = node[i].w;52 if (!same (x, y)) {Union (x, y); sum += w;}53 }54 printf ("%d\n", sum);55 }56 }