最经典：赤祼祼的最小生成树:hdu1233还是畅通工程

Problem Description

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

 

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

 

Output

对每个测试用例，在1行里输出最小的公路总长度。

 

Sample Input

3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

 

Sample Output

3
5

/*
 * Introduction to Algorithms
 * Chapter 23 --- MST.Kruskal
 */

#include <iostream>
#include <algorithm>
using namespace std;

const int maxint = 999999;

typedef struct Road{
    int c1, c2;   // a到b
    int value;  // 权值
}Road;



Road road[50005];//（N<100hdu输入数据超出100） 设一个比较大的值，实际看输入最小生成树中：边数e=n-1
int node[50006];//最小生成树：n顶点数

bool myCmp(const Road &a, const Road &b)
{
    if(a.value < b.value)
        return 1;
    return 0;
}

//node[2]=1 node[8]=1 ,node[3]=1,共同的祖先,如果(3,8)加进去，则构成回路，不要
//有点像并查集
int Find_Set(int n)
{
    if(node[n] == -1)
        return n;
    return node[n] = Find_Set(node[n]);
}

bool Merge(int s1, int s2)
{
    int r1 = Find_Set(s1);
    int r2 = Find_Set(s2);
    if(r1 == r2)//如果相等证明构成回路，则直接返回一个0,不要把顶点加进来(下一步是加进去的)
        return 0;
    if(r1 < r2)
        node[r2] = r1;
    else
        node[r1] = r2;
    return 1;
}

int main()
{

    int no;//实际的点
    while(scanf("%d",&no)!=EOF && no)
    {
        //初始化全为-1
        memset(node, -1, sizeof(node));
        int line;//记录实际关系数
        line=no*(no-1)/2;
        int i;
        for(i=0; i<line; ++i)
        {
            scanf("%d%d%d",&road[i].c1,&road[i].c2,&road[i].value);
        }
        sort(road, road+line, myCmp);//按权值升序排序
        int sum = 0, count = 0;  // sum是MST的值，count是记录已使用的点数
        for(i=0; i<line; ++i)
        {
            if(Merge(road[i].c1, road[i].c2))//如果返回的为0,则证明构成回路，不要加进
             {
                count ++;
                sum += road[i].value;
            }
            if(count == no-1)//e=n-1已经连通，可以退出
                break;
        }
        cout << sum << endl;
    }
    return 0;
}