POJ 1251 Networking （kruskal最小生成树）

题目意思：
给出若干个镇， 镇用一个大写字母表示，有若干条边，要求最小生成树，使得边总和最小；
最小生成树，裸题

本题要点：
1、直接使用 kruskal 算法，计算出最小生成树每一段的距离总和

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 30;
int graph[MaxN][MaxN];
int n, tot, ans;
int fa[MaxN];struct rec
{
    int x, y, z;bool operator<(const rec& rhs) const{
    return z < rhs.z;}
}edges[MaxN * MaxN];int get(int x)
{
    if(x == fa[x]){
    return x;}return fa[x] = get(fa[x]);
}int main()
{
    char a[2] = {
    0}, b[2] = {
    0};int m, d;while(scanf("%d", &n) != EOF && n){
    tot = 0, ans = 0;for(int i = 1; i < n; ++i){
    scanf("%s%d", a, &m);	for(int j = 0; j < m; ++j){
    scanf("%s%d", b, &d);	edges[++tot].x = a[0] - 'A' + 1, edges[tot].y = b[0] - 'A' + 1;edges[tot].z = d;}}sort(edges + 1, edges + tot + 1);for(int i = 1; i <= n; ++i){
    fa[i] = i;}for(int i = 1; i <= tot; ++i){
    int x = get(edges[i].x);int y = get(edges[i].y);if(x == y){
    continue;}fa[x] = y;ans += edges[i].z;}printf("%d\n", ans);}return 0;
}/* 9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0 *//* 216 30 */