题目链接: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;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告