POJ 1251 Jungle Roads(Kruskal)

テーマリンク:[[kuangbin带你飞]テーマ六最小生成木A-Jungle Roads(http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66965#problem/A)
Kruskalアルゴリズム最小生成ツリーを求める

タイトル:
図の最小生成木を求めて、主に入力に注意します!!Kruskalアルゴリズム:セット+ソートを調べます

//#include"stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;

struct edge
{
    int s, e;
    int w;
}e[100];//  

int n;
int cnt = 0;
int p[30];//   

bool cmp(edge a, edge b) { return a.w < b.w;}
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }//    

int kruskal()
{
    sort(e, e + cnt, cmp);

    int ans = 0;
    for (int i = 0; i < cnt; i++)
    {
        int x = find(e[i].s);
        int y = find(e[i].e);
        if (x != y)//     （    ）
        {
            ans += e[i].w;
            p[x] = y;
        }
    }
    return ans;
}

int main()
{
    while (cin >>n)
    {
        if (n == 0) break;

        cnt = 0;
        for (int i = 0; i < 30; i++) p[i] = i;
        for (int i = 0; i < n-1; i++)
        {//  n-1     ,wrong N ！！！   ！
            char s;
            cin >> s;
            int k;
            cin >> k;
            for (int j = 0; j < k;  j++)
            {
                char end;
                int w;
                cin >> end>>w;
                e[cnt].s = s - 'A';
                e[cnt].e = end - 'A';
                e[cnt++].w = w;
            }               
        }
        int ans = kruskal();
        printf("%d
", ans);
    }
    return 0;
}