学步园

        最小生成树模板题，不再敖述。

       代码如下：

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#define mem(a , b ) memset(a , b , sizeof(a))
using namespace std ;
const int MAXN = 1000 ;
int n ;
struct Edge
{
    int a ;
    int b ;
    int d ;
} e[MAXN] ;
int set[30] ;
int cnt = 0 ;
int find(int x)
{
    int r = x ;
    while (r != set[r] )
    {
        r = set[r] ;
    }
    return r ;
}
bool cmp(Edge x , Edge y)
{
    return x.d < y.d ;
}
void init()
{
    cnt = 0 ;
    int i ;
    char A , B ;
    int k ;
    int td ;
    for(i = 0 ; i < n - 1 ; i ++)
    {
        cin >> A ;
        scanf("%d" , &k) ;
        //cout << "k : " << k << endl ;
        int j ;
        for(j = 0 ; j < k ; j ++)
        {
            cin >> B ;
            scanf("%d" , &td) ;
            //cout << "td : " << td << endl ;
            e[cnt].a = A - 'A' ;
            e[cnt].b = B - 'A' ;
            e[cnt ++].d = td ;
        }
    }
    for(i = 0 ; i < n ; i ++)
        set[i] = i ;
}
void solve()
{
    sort(e , e + cnt , cmp) ;
    int i ;
    int ans = 0 ;
    int ct = 0 ;
    for(i = 0 ; i < cnt ; i ++)
    {
        int ta = find(e[i].a) ;
        int tb = find(e[i].b) ;
        if(ta != tb)
        {
            if(ta < tb) set[tb] = ta ;
            else
                set[ta] = tb ;
            ans += e[i].d ;
            cnt ++ ;
        }
        if(cnt == n - 1)
        break ;
    }
    printf("%d\n" , ans) ;
}
int main()
{
    while (scanf("%d" , &n) != EOF)
    {
        if(n == 0) break ;
        init() ;
        solve() ;
    }
    return 0 ;
}