///////////////////////////////////////// //作品名称:并查集的实现及应用 //作者姓名:梁岳传//作品时间:2008-8-15//最后修改:2008-8-15 //Q Q 号码:280282813 //版权所有,翻版必究 ///////////////////////////////////////// #include<iostream> using namespace std; class Set{private: int* ary; int length;public: int Find(int index); bool Union(int first, int second); Set(int n); virtual ~Set(){delete[]ary;} }; Set::Set(int n){ int i; ary = new int[n]; length = n; for(i = 0; i < n; ++i) ary[i] = -1;} //将每次查找过的路线上的结点全部都指向根结点int Set::Find(int index){ int i, j, t; if(index < 0 || index >= length) return -1; //查找index元素的根结点 for(i = index; ary[i] >= 0; i = ary[i]); //将这条路线上的所有元素全部指向根结点 for(j = index; j != i; j = t){ t = ary[j]; ary[j] = i; } return i;} //树的根结点保存树的元素个数,以负值的形式保存bool Set::Union(int first, int second){ int i, j; if(first < 0 || first >= length) return false; if(second < 0 || second >= length) return false; //寻找两个元素所在树的根结点 i = Find(first); j = Find(second); //越过边界或者两个元素已经在同一棵树中 if(i == -1 || j == -1 || i == j) return false; //如果第i棵树的元素比第j棵树的元素要多则将j加入到i中 if(ary[i] < ary[j]){ ary[i] += ary[j]; ary[j] = i; } //否则将i加入到j中 else{ ary[j] += ary[i]; ary[i] = j; } return true;} typedef struct{ int weight; int f; int s;}Edge; int cmp(const void*c, const void*d){ Edge *a = (Edge*)c; Edge *b = (Edge*)d; return a->weight - b->weight;}int main(int argv, char* argc[]){ int i, j, num, n, ct; char fch, sch; double MinCost; Edge edges[100]; while(1) { cin>>num; if(num == 0) break; ct = 0; for(i = 0; i < num-1; ++i){ cin>>fch; cin>>n; for(j = 0; j < n; ++j){ cin>>sch; cin>>edges[ct].weight; edges[ct].f = fch-'A'; edges[ct].s = sch-'A'; ct++; } getchar(); } qsort(edges, ct, sizeof(Edge), cmp); Set set(30); MinCost = 0; for(i = 0; i < ct; ++i){ if(set.Union(edges[i].f, edges[i].s) == true) MinCost += edges[i].weight; } cout<<MinCost<<endl; } return 0;} //测试题://http://acm.hdu.edu.cn/showproblem.php?pid=1301 //测试数据：/*9A 2 B 12 I 25B 3 C 10 H 40 I 8C 2 D 18 G 55D 1 E 44E 2 F 60 G 38F 0G 1 H 35H 1 I 353A 2 B 10 C 40B 1 C 200*///测试结果/*21630*/
评论