首页 > 代码库 > poj 1251 Jungle Roads
poj 1251 Jungle Roads
题目链接：http://poj.org/problem?id=1251
思路：
使用最小生成树算法，可以求解。需要注意的树Kruskal算法中使用了并查集，对于并查集用法需要注意。
代码：
#include <iostream>#include <algorithm>using namespace std;const int N = 30, M = 100;int S[N];int Index, n;typedef struct { int U, V, W; }Edge;Edge E[M];bool cmp( Edge a, Edge b ) { return a.W < b.W; }int Find( int X ){ if ( S[X] <= 0 ) return X; else return S[X] = Find( S[X] );}void SetUnion( int Root1, int Root2 ){ int Rank_Root1 = Find( Root1 ); int Rank_Root2 = Find( Root2 ); int Tmp = S[Rank_Root1] + S[Rank_Root2]; if ( S[Rank_Root1] < S[Rank_Root2] ) { S[Rank_Root2] = Rank_Root1; S[Rank_Root1] = Tmp; } else { S[Rank_Root1] = Rank_Root2; S[Rank_Root2] = Tmp; }}int Kruskal(){ int Ans = 0, Cnt = 0; memset( S, -1, sizeof(S) ); for ( int i = 0; i < Index; i++ ) { int U = E[i].U; int V = E[i].V; int SetU = Find( U ); int SetV = Find( V ); if ( Find(U) != Find(V) ) { Cnt++; Ans += E[i].W; SetUnion( U, V ); }if ( Cnt >= n - 1 ) break; } return Ans;}int main(){ int w; int Ans, Num; char u, v; while ( cin >> n ) { if ( n == 0 ) break; Index = 0; for ( int i = 0; i < n-1; ++i ) { cin >> u >> Num; for ( int j = 0; j < Num; ++j ) { cin >> v >> w; E[Index].U = u - ‘A‘; E[Index].V = v - ‘A‘; E[Index].W = w; Index++; } } sort( E, E+Index, cmp ); Ans = Kruskal(); cout << Ans << endl; } return 0;}
poj 1251 Jungle Roads
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。