题目描述：

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

输入：

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

输出：

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

样例输入：

样例输出：

3
5

代码：

Kruskal

#include <iostream>  
#include <algorithm>  
using namespace std;  
struct Node  
{  
int startPoint;  
int endPoint;  
int length;  
} nodes[5000];  
bool cmp(const Node A,const Node B)  
{  
return A.length<B.length;  
}  
int father[100];  
int findSet(int num)  
{  
//其实就是获取到分组的最初始的点的信息;  
if(father[num]!=num)  
    return findSet(father[num]);  
else          
    return father[num];  
}  
bool UnionSet(int x,int y)  
{  
int tmpx=findSet(x);  
int tmpy=findSet(y);  
if(tmpy==tmpx)//因为两个已经是一个组了;  
    return false;  
father[tmpy]=tmpx;//如果可以合并，这里只需要更新其前驱节点，因为他最终还是会找到之前的组;  
return true;  


}  
int main()  
{  
int num;  
while(cin>>num&&num)  
{  
    for(int i=1;i<=num;i++)  
        father[i]=i;  
    int tmp=num*(num-1)/2;  
    for (int i=0;i<tmp;i++)  
        cin>>nodes[i].startPoint>>nodes[i].endPoint>>nodes[i].length;  
    sort(nodes,nodes+tmp,cmp);  
    int result=0,count=0;  
    for (int i=0;i<tmp;i++)  
    {  
        if(UnionSet(nodes[i].startPoint,nodes[i].endPoint))  
        {  
            result=result+nodes[i].length;  
            count++;  
            if(count+1==num)  
                break;  
        }  
    }  
    cout<<result<<endl;  
}  
return 0;  
}

Prim 可以和Dijkstra对比，会发现惊人的相似，Dijkstra只是多维护了一个点到点的距离，而Prim只需要维护最短距离

#include <iostream>  
#include <algorithm>  
using namespace std;  
int A[100][100],low[100];  
bool visited[100];  
int MaxInt=1232000;  
int Prim(int num)  
{  
int minDis,result=0;  
int ppre=1;  
for (int i=1;i<=num;i++)  
{  
    low[i]=A[1][i];  
}  
visited[ppre]=true;  
for (int i=1;i<num;i++)  
{  
    minDis=MaxInt;  
    for (int j=1;j<=num;j++)//找到最小;  
    {  
        if(!visited[j]&&low[j]<minDis)  
        {  
            minDis=low[j];  
            ppre=j;  
        }  
    }  
    result=result+minDis;  
    for (int j=1;j<=num;j++)  
    {  
        if(!visited[j]&&A[ppre][j]<low[j])  
            low[j]=A[ppre][j];  
    }  
    visited[ppre]=true;  
}  
return result;  
}  
int main()  
{  
int num;  
while(cin>>num&&num)  
{  
    for(int i=1;i<=num;i++)  
    {  
        visited[i]=false;  
        for (int j=1;j<=num;j++)  
        {  
            A[i][j]=MaxInt;  
        }  
    }  
    int tmp=num*(num-1)/2,x,y,z;  
    for (int i=0;i<tmp;i++)  
    {  
        cin>>x>>y>>z;  
        A[y][x]=A[x][y]=z;  
    }  
    cout<<Prim(num)<<endl;  
}  
return 0;  
}