#include<iostream>
using namespace std;
#define INF 0x3f3f3ff
const int MAX_V_NUM=105;
int Edges[MAX_V_NUM][MAX_V_NUM];
struct Node{
int adjvex;//存储该边依附在U中的顶点
int lowcost;//边的权值，访问标记
}closedge[MAX_V_NUM];
int prim(int u,int n)
{
int i,j,k,min,sum=0;
for(i=1;i<=n;i++)
{
closedge[i].adjvex=u;
closedge[i].lowcost=Edges[u][i];
}
closedge[u].lowcost=-1;
for(i=1;i<n;i++)
{
min=INF;
for(j=1;j<=n;j++)
if(closedge[j].lowcost!=-1&&closedge[j].lowcost<min)
{
min=closedge[j].lowcost;
k=j;
}
//cout<<"("<<closedge[k].adjvex<<","<<k<<","<<min<<")"<<endl;
sum+=min;
closedge[k].lowcost=-1;
for(j=1;j<=n;j++)//修改其他顶点的最小边
{
if(Edges[k][j]!=0&&Edges[k][j]<closedge[j].lowcost)
{
closedge[j].adjvex=k;
closedge[j].lowcost=Edges[k][j];
}
}
}
cout<<sum<<endl;
return 0;
}
int main()
{
int n,i,j,u,v,w;
while(true)
{
cin>>n;
if(n==0)
break;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j)
Edges[i][j]=0;
else
Edges[i][j]=INF;
}
for(i=1;i<=(n*(n-1))/2;i++)
{
cin>>u>>v>>w;
Edges[u][v]=Edges[v][u]=w;
}
prim(1,n);
}
return 0;
}
转载于:https://www.cnblogs.com/-wang-xin/archive/2012/12/07/2807474.html