POJ1287 Networking-白红宇

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

复制代码

#include <iostream>

#include <limits>

using namespace std;

const int MAX_VETEX_NUM = 100;

int nPoints,nRoutes;//点的个数，边的个数

int route[MAX_VETEX_NUM][MAX_VETEX_NUM]; //图

int closedge[MAX_VETEX_NUM];

int prim()

{//普里姆算法求最小生成树

int i,j,sum = 0;

int v[MAX_VETEX_NUM];//选择的顶点集

int k = 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)

{

int min = 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];

}

return sum;

}

int main()

{

int i,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;

}

return 0;

}

复制代码

本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2009/09/12/1565282.html，如需转载请自行联系原作者