poj 1251 Jungle Roads MST

   水

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define INF 1E9
using namespace std;
int fa[30];
int far(int nn)
{
    if(fa[nn]<0)return nn;
    return fa[nn]=far(fa[nn]);
}
struct edge
{
    int v,a,b;
};
edge e[80];
bool cmp(edge a,edge b)
{
    return a.v<b.v;
}
int main()
{
    int n,i,j,m,v,a,b;
    char t;
    while(~scanf("%d",&n)&&n)
    {
        int K=0;
        memset(fa,-1,sizeof(fa));
        for(i=0;i<n-1;i++)
        {
            scanf(" %*c%d",&m);
            for(j=0;j<m;j++)
            {
               scanf(" %c%d",&t,&v);
               e[K++]=edge{v,i,t-'A'};
            }
        }
        sort(e,e+K,cmp);
        int ans=0;
        for(i=1,j=0;i<n;j++)
        {
            a=far(e[j].a);
            b=far(e[j].b);
            if(a==b)continue;
            fa[b]=a;ans+=e[j].v;
            i++;
        }
        printf("%d\n",ans);
    }
}