某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 

Input

测试输入包含若干测试用例。

每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 

当N为0时，输入结束，该用例不被处理。 

Output

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

Sample Input

31 2 11 3 22 3 441 2 11 3 41 4 12 3 32 4 23 4 50

Sample Output

35Huge input, scanf is recommended. 下面有一些我写代码时使用到的代码变量： 邻接矩阵（Adjacency Matrix） 无穷大（infinite） 顶点（vertex） 权值（cost） 初始化（initialize） 临时工（temp） 整型最大数值=0x7fffffff AC代码： 1.prim算法

#include
     
      #include
      
       #define N 110#define inf 0x7fffffffint cost[N][N];int ver[N];int n,a,b,l,temp,v,k=1;using namespace std;int initia(){
   //顶点及储存权值的邻接矩阵的初始化        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++){                if(i==j) cost[i][j]=0;                else cost[i][j]=inf;                ver[i]=0;            }             ver[1]=1;             return 0;}int prim(){    int sumcost=0,mincost;    int temp,v;    for(int vsum=1;vsum
       
        >n&&n!=0){            initia();            int t=n*(n-1)/2;            while(t--){                cin>>a>>b>>l;                cost[a][b]=cost[b][a]=l;        }    prim();    }    return 0;}
       
      
     

用于记录的数组的下标是从1开始的，且注意红色标记地方，vsum的循环次数不要增加,否则会出错！

这里还有一份其他人的代码，红色部分大大减少了运行时的重复次数，没太看懂！

 

#include
     
      #include
      
       #define INF 99999999#define N 110using namespace std;int n,G[N][N];void prim(){    int p[N],vis[N],i,j,v,sum,m,last,k =0;    p[k++] = 1;    sum = 0;    for(i=1;i<=n;i++) vis[i]=0;    vis[1] = 1;    for(m=1;m
      
     

 2.kruskal算法

这个代码还没有过，我还在找原因

先存着

#include
     
      #include
      
       #define N 110#define inf 0x7fffffffint cost[N][N];int ver[N];int n,a,b,l,tempi,tempj;using namespace std;int initia(){
   //顶点及储存权值的邻接矩阵的初始化        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++){                if(i==j) cost[i][j]=0;                else cost[i][j]=inf;                ver[i]=0;            }             return 0;}int judge(int i,int j){    if(ver[i]==1&&ver[j]==1) return 0;    else return 1;}int kruskal(){    int sumcost=0,mincost;    for(int esum=0;esum
       
        >n&&n!=0){            initia();            int t=n*(n-1)/2;            while(t--){                cin>>a>>b>>l;                cost[a][b]=cost[b][a]=l;        }    kruskal();    }    return 0;}