1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<algorithm> 5 using namespace std; 6 const int inf=0x3f3f3f3f;///当两个点之间没有边时设置这两个边之间的距离为无穷大 7 const int maxn=110;///数组的长度 8 int ma[maxn][maxn],lowcost[maxn];///ma[i][j]数组的用于存储i,j两点之间的距离，lowcast[j]用于存储从标记边k到边j的边的长度 9 bool vis[maxn];///用于记录点是否已经加入到树中10 int nodenum,sum;11 void prim()12 {13 int temp,k;14 sum=0;15 memset(vis,false,sizeof(vis));16 vis[1]=true;///从1开始查询17 for(int i=1;i<=nodenum;i++)18 {19 lowcost[i]=ma[1][i];20 21 }22 for(int i=1;i<=nodenum;i++){23 temp=inf;///temp用于存储最短的距离24 for(int j=1;j<=nodenum;j++){25 if(!vis[j]&&temp>lowcost[j])26 temp=lowcost[k=j];///在赋值的同时把j的值赋给k，下次就从k开始向其他结点寻找27 if(temp==inf)break;///如果temp值没有改变的话就证明该点不与其它点连通，最小生成树建立失败，跳出循环28 vis[k]=true;29 sum+=temp;30 for(int j=1;j<=nodenum;j++){31 if(!vis[j]&&lowcost[j]>ma[k][j])///此时lowcast中其实还含有上一个结点到j的距离，若ma[k][j]不足够小的话lowcast的值将不变32 lowcost[j]=ma[k][j];33 }34 }35 }36 37 }38 int main()39 {40 int a,b,cost,edgenum;41 while(cin>>nodenum&&nodenum){42 memset(ma,inf,sizeof(ma));///初始化最开始所有的点之间都不关联43 edgenum=nodenum*(nodenum-1)/2;///edgenum是所有点之间都有边相连的边的个数44 for(int i=1;i<=edgenum;i++){45 cin>>a>>b>>cost;46 if(cost<ma[a][b]){47 ma[a][b]=ma[b][a]=cost;///无向图的边没有方向48 }49 }50 prim();51 cout<<sum<<endl;52 }53 }