//用并查積 和 克魯是卡爾算法實現查找最短邊
//利用快排按邊遞增排列，每次從中選出最短邊,同時將最短邊的兩個頂點并入到集合中
心得：利用并查積 和 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
雪黛依夢 閱讀(405)
評論(0) 編輯 收藏 引用 所屬分類:
最小生成樹 、
并查積