HDU1301 Jungle Roads(克鲁斯卡尔算法版)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1301

通过对数组构造一个静态链表，将在同一个连通分量中的顶点链接起来。对按边权值从大到小排序后的边集合逐条进行判断，若边的起点和终点分别在不同的连通分量链表中（这通过获取其所在链表的表尾元素是否是同一个来进行判定），则此边加入最小生成树的边集合中，并将边的终点加入到边的起点所在的静态链表中。最终所有结点都会链接到一个静态链表中。

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->#include<iostream>
#include<string>
#include<algorithm>
usingnamespacestd;

constintMAX_VETEXT_NUM=26;//最大的顶点数
constintMAX_EDGE_NUM=75;//最大的边数

structEdge
{
intbegin;//起点
intend;//结点
doublecost;//边的权值
};

Edgeedge[MAX_EDGE_NUM];//边集合
doublesum=0;
intConnectedList[MAX_VETEXT_NUM];//连通分量静态链表
intnEdges;//边的数目
intnVetexs;//顶点数目

intFindInConnectList(intPoint[],intv)
{//若v所在的连通分量静态链表为空，则返回参数v,否则返回其所在链表的表尾元素,
inti=v;
while(Point[i]>0)
i=Point[i];
returni;
}

boolcmp(constEdge&a,constEdge&b)
{//根据边权值从小到大排序
returna.cost<b.cost;
}

voidKruscal()
{
inti,j;
intv1,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;//处理完一条边
}
}

intmain()
{
inti,j;
intnum;
doublecost;
charchStart,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;
}
return0;
}