HDU1301 Jungle Roads(普里姆算法版)

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2403

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->#include<iostream>
#include<limits>
usingnamespacestd;

intn;
constintMAX_VETEXT_NUM=27;
intmap[MAX_VETEXT_NUM][MAX_VETEXT_NUM];
intclosedge[MAX_VETEXT_NUM];

intprim()
{
intv[MAX_VETEXT_NUM];//顶点集合
inti,j,k,sum;
sum=0;
k=0;//初始点为'A'
for(i=0;i<MAX_VETEXT_NUM;++i)
{
if(i!=k)
{
closedge[i]=map[k][i];
v[i]=0;
}
}
v[k]=1;//'A'点并入集合中
for(i=1;i<MAX_VETEXT_NUM;++i)
{
intmin=numeric_limits<int>::max();
//选择k
for(j=0;j<MAX_VETEXT_NUM;++j)
{
if(!v[j]&&(closedge[j]!=0)&&(closedge[j]<min))
{
min=closedge[j];
k=j;
}
}
if(min==numeric_limits<int>::max())
{
break;
}
sum+=min;
v[k]=1;//k个顶点并入集合
//从k顶点出发有更短的边
for(j=0;j<MAX_VETEXT_NUM;++j)
{
if(map[k][j]<closedge[j])
{
closedge[j]=map[k][j];
}
}
}
returnsum;
}
intmain()
{
inti,j;
charchStart,chEnd;
intnOutEdges,nValue;
while(cin>>n&&n!=0)
{
//初始化图
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
map[i][j]=map[j][i]=numeric_limits<int>::max();
}
}
for(i=0;i<n-1;++i)
{
cin>>chStart>>nOutEdges;
for(j=0;j<nOutEdges;++j)
{
cin>>chEnd>>nValue;
map[chStart-'A'][chEnd-'A']=nValue;
map[chEnd-'A'][chStart-'A']=nValue;
}
}
cout<<prim()<<endl;
}
return0;
}