/////////////////////////////////////////
//作品名称:并查集的实现及应用

//作者姓名:梁岳传
//作品时间: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

//测试数据：
/*
9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0
*/
//测试结果
/*
216
30
*/

评论