//用并查积 和 克鲁是卡尔算法实现查找最短边
//利用快排按边递增排列，每次从中选出最短边,同时将最短边的两个顶点并入到集合中
心得：利用并查积 和 kruskal算法结合找最短路径可以使查找的效率更高
本题的关键是正确地设定好两个数组，一个是用于存放顶点边值的node1，另一个是用于并查积处理的node2，并且将这两个数组联系好
加入集合中的边都是构成最小生成树的边，所以每家一次sum 都要加上这两个顶点之间的距离
#include <iostream>
#include <string>
using namespace std;
struct node1 //用于存放顶点和边值
{
int x;
int y;
int distance;
};
node1 edge[5010]; // n 个顶点的边无向图最多有 n * (n - 1) / 2 条边
struct node2 //并查积数组
{
int parent;
int height;
};
node2 village[100];
bool cmp ( const node1 &a, const node1 &b )
{
return a.distance < b.distance;
}
//并查积初始化
void set ( int n )
{
for ( int i = 1; i <= n; i++)
{
village[i].parent = i;
}
}
//找根节点
int findfather (int a)
{
while ( a != village[a].parent ) //理解while 树状结构：找到最终的跟节点
a = village[a].parent;
return a;
}
//合并到同一集合
void merge (int a, int b) //注意参数：要合并两个节点的根
{
if ( village[a].height == village[b].height )
{
village[b].parent = a;
village[a].height ++;
}
//小树合并到大树
else if ( village[a].height > village[b].height )
{
village[b].parent = a;
}
else
village[a].parent = b;
}
int main ()
{
int n, k;
int x, y, d;
int a, b;
while ( scanf ("%d", &n ) != EOF && n )
{
set ( n );
memset ( edge, 0, sizeof (edge) );
//输入处理
k = n * ( n - 1 ) / 2;
for ( int i = 0; i < k; i ++ )
{
scanf ( "%d %d %d", &x, &y, &d );
edge[i].x = x;
edge[i].y = y;
edge[i].distance = d;
}
//排序
sort ( edge, edge + k, cmp );
//从已排好的序列中选出最短边同时利用并查积构建图
int sum = 0;
for ( int i = 0; i < k; i++ )
{
a = findfather ( edge[i].x );
b = findfather ( edge[i].y );
if ( a != b )
{
merge ( a, b );
sum += edge[i].distance;
}
}
printf ( "%d\n", sum );
}
//system ("pause");
return 0;
}
posted on 2010-08-26 16:02
雪黛依梦 阅读(380)
评论(0) 编辑 收藏 引用 所属分类:
最小生成树 、
并查积