HDU1301

hdu1301.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define sd(x) scanf("%d",&x)
#define sdd(x,y) scanf("%d%d",&x,&y)
#define sddd(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
using namespace std;

int n;
struct road
{
    int u,v,w;
} r[900];

bool cmp(road a,road b)
{
    return a.w<b.w;
}

class Disjoint
{
    int dsj[30];
public:
    Disjoint();
    void init();
    int Find(int);
    void Union(int,int);
};

void Disjoint::init()
{
    for (int i=0; i<30; i++) dsj[i]=i;
}

Disjoint::Disjoint()
{
    init();
}

int Disjoint::Find(int x)
{
    return dsj[x]==x?x:dsj[x]=Find(dsj[x]);
}

void Disjoint::Union(int a,int b)
{
    int fa=Find(a),fb=Find(b);
    dsj[fa]=fb;
}

int Kruskal(road *a,Disjoint &d)
{
    int cur=0,ans=0,roads=0;
    while(roads<n-1)
    {
        if (d.Find(r[cur].u)!=d.Find(r[cur].v))
        {
            ans+=r[cur].w;
            d.Union(r[cur].u,r[cur].v);
            roads++;
        }
        cur++;
    }
    return ans;
}

int main()
{
    Disjoint d;
    while(~sd(n)&&n)
    {
        d.init();
        int cur=0;
        char dst;
        char from;
        int prc,nor;
        for (int i=0; i<n-1; i++)
        {
            cin >> from >> nor;
            while(nor--)
            {
                cin >> dst>>prc;
                r[cur].u=from-'A';
                r[cur].v=dst-'A';
                r[cur++].w=prc;
            }
        }
        sort(r,r+cur,cmp);
        cout <<Kruskal(r,d) << endl;

    }
}