1251:Jungle Roads

keyword

MST　Kruskal　Union-Find　C++

概要

問題文は読んでないけど図だけ見てMSTだと決め打ち。連結性だけ確認して実装にかかる。改行コードの処理とかで手間取ったけどMST自体は最近よく書くのですんなり書けた。

typedef pair<int, pair<int, int> > edge;

int pars[26];

int getRoot(int x){
    if( x==pars[x] ) return x;
    else return pars[x] = getRoot(pars[x]);
}

bool isSame(int x, int y){
    return getRoot(x) == getRoot(y);
}

void merge(int x, int y){
    int xx = getRoot(x), yy = getRoot(y);
    pars[xx] = yy;
    return ;
}

int main(){
    char c, to;
    int d, a, i, n, nn, j;
    while(scanf("%d\n",&n)){
        if(!n) break;
        priority_queue<edge, vector<edge>, greater<edge> > Q;
        REP(i,26)pars[i]=i;
        REP(i,n-1){
            scanf("%c %d", &c, &nn);
            if(!nn)scanf("\n");
            REP(j,nn){
                if(j<nn-1) scanf(" %c %d",&to,&d);
                else scanf(" %c %d\n",&to,&d);
                Q.push(MP(d,MP(c-'A', to-'A')));
            }
        }
        int total = 0, cnt = 0;
        while(!Q.empty() && cnt < n-1){
            edge t = Q.top();
            if(!isSame(t.sc.fs, t.sc.sc)){
                merge(t.sc.fs, t.sc.sc);
                total += t.fs;
                cnt++;
            }
            Q.pop();
        }
        printf("%d\n", total);
    }
    return 0;
}