题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1301
通过对数组构造一个静态链表，将在同一个连通分量中的顶点链接起来。对按边权值从大到小排序后的边集合逐条进行判断，若边的起点和终点分别在不同的连通分量链表中（这通过获取其所在链表的表尾元素是否是同一个来进行判定），则此边加入最小生成树的边集合中，并将边的终点加入到边的起点所在的静态链表中。最终所有结点都会链接到一个静态链表中。
复制代码
#include<iostream>
#include<string>
#include<algorithm>
using namespace std ;
const int MAX_VETEXT_NUM = 26;//最大的顶点数
const int MAX_EDGE_NUM = 75;//最大的边数
struct Edge
{
int begin;//起点
int end;//结点
double cost;//边的权值
};
Edge edge[MAX_EDGE_NUM];//边集合
double sum = 0;
int ConnectedList[MAX_VETEXT_NUM];//连通分量静态链表
int nEdges; //边的数目
int nVetexs; //顶点数目
int FindInConnectList( int Point[] , int v)
{//若v所在的连通分量静态链表为空，则返回参数v,否则返回其所在链表的表尾元素,
int i = v ;
while ( Point[i] > 0 )
i = Point[i];
return i ;
}
bool cmp( const Edge& a , const Edge& b )
{//根据边权值从小到大排序
return a.cost < b.cost ;
}
void Kruscal()
{
int i , j ;
int v1 , v2 ;
//初始化连通分量静态链表
for ( i = 0 ; i < nVetexs ; i++ )
{
ConnectedList[i] = 0 ;
}
i = 0 ; j = 0 ;
while ( j < nVetexs - 1 && i < nEdges )
{
v1 = FindInConnectList( ConnectedList , edge[i].begin) ;
v2 = FindInConnectList( ConnectedList , edge[i].end) ;
if ( v1 != v2)
{//起点和终点不在同一个连通分量重
sum += edge[i].cost;
ConnectedList[v1] = v2 ;//加入连通分量链表中
++j;//最小生成树边数加1
}
++i;//处理完一条边
}
}
int main()
{
int i , j ;
int num ;
double cost ;
char chStart , chEnd;
while ( cin >> nVetexs && nVetexs != 0)
{
sum = 0 ;
nEdges = 0 ;
for ( i = 0 ; i < nVetexs - 1 ; i ++ )
{
cin >> chStart >> num ;
for( j = 0 ; j < num ; j ++ )
{
cin >> chEnd >> cost ;
edge[nEdges].begin = chStart - 'A' ;
edge[nEdges].end = chEnd - 'A' ;
edge[nEdges].cost = cost ;
nEdges ++;
}
}
sort(edge , edge + nEdges, cmp) ;
Kruscal() ;
cout << sum << endl ;
}
return 0 ;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2009/09/13/1566016.html，如需转载请自行联系原作者
