题目链接：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，如需转载请自行联系原作者
![[POJ 1236] Network of Schools | Tarjan缩点](https://ucc.alicdn.com/pic/developer-ecology/5061455e3b1a4fa2889be2fab9472b9b.png?x-oss-process=image/resize,h_160,m_lfit)