`
phinecos
  • 浏览: 339908 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

POJ1287 Networking

 
阅读更多

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

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

constintMAX_VETEX_NUM=100;
intnPoints,nRoutes;//点的个数,边的个数
introute[MAX_VETEX_NUM][MAX_VETEX_NUM];//
intclosedge[MAX_VETEX_NUM];

intprim()
{
//普里姆算法求最小生成树
inti,j,sum=0;
intv[MAX_VETEX_NUM];//选择的顶点集
intk=1;//初始点为号顶点
for(i=1;i<=nPoints;++i)
{
if(i!=k)
{
closedge[i]
=route[1][i];
v[i]
=0;
}
}
v[k]
=1;//1号点并入顶点集
for(i=1;i<=nPoints;++i)
{
intmin=numeric_limits<int>::max();
//选当前顶点集中顶点到其他顶点的最短边
for(j=1;j<=nPoints;++j)
{
if(!v[j]&&closedge[j]&&(closedge[j]<min))
{
//还没并入过顶点集,有到顶点集中顶点的边
min=closedge[j];
k
=j;
}
}
if(min!=numeric_limits<int>::max())
sum
+=min;
v[k]
=1;//第k顶点并入顶点集
//从k顶点出发有更短边,
for(j=1;j<=nPoints;j++)
{
if(!v[j]&&route[k][j]&&((route[k][j]<closedge[j])||closedge[j]==0))
{
closedge[j]
=route[k][j];
}
}
}
returnsum;
}
intmain()
{
inti,p1,p2,nCost;
while(cin>>nPoints&&nPoints!=0)
{
cin
>>nRoutes;
if(nRoutes==0)
{
cout
<<0<<endl;
}
else
{
memset(route,
0,sizeof(route));
for(i=1;i<=nRoutes;++i)
{
cin
>>p1>>p2>>nCost;
if(route[p1][p2]!=0)
{
if(nCost<route[p1][p2])
{
route[p1][p2]
=route[p2][p1]=nCost;
}
}
else
{
route[p1][p2]
=route[p2][p1]=nCost;
}
}
cout
<<prim()<<endl;
}
}
return0;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics