题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2403
复制代码
#include <iostream>
#include <limits>
using namespace std;
int n;
const int MAX_VETEXT_NUM = 27;
int map[MAX_VETEXT_NUM][MAX_VETEXT_NUM];
int closedge[MAX_VETEXT_NUM];
int prim()
{
int v[MAX_VETEXT_NUM];//顶点集合
int i,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)
{
int min = 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];
}
}
}
return sum;
}
int main()
{
int i,j;
char chStart,chEnd;
int nOutEdges,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;
}
return 0;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2009/09/13/1565759.html，如需转载请自行联系原作者
