poj 1251

直接prim就ac了。
这里简单描述一下prim算法：
把点分成两堆，一堆是已经连好路径的，已visit，另一堆是还未访问过的点。
我们每次都从未访问过的点里选一个到已访问过的点集距离最短的点，把它放到已访问的点集中，并且更新low数组。
这就是一个贪心的思想，每次连上的边都是剩下的边中最短的。

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX 100
#define INF 0x3f3f3f3f
using namespace std;

int n;
int count, e, len;
char c, d;
int map[MAX][MAX];
int visit[MAX];
int low[MAX];

int prim() {
  int sum = 0;
  memset(visit, 0, sizeof(visit));
  visit[0] = 1;
  for (int i = 0; i < n; i++) {
    low[i] = map[0][i];
  }

  int u;
  for (int i = 0; i < n - 1; i++) {
    int minn = INF;

    for (int j = 0; j < n; j++) {
      if (!visit[j] && low[j] < minn) {
        minn = low[j];
        u = j;
      }
    }

    visit[u] = 1;
    sum += minn;

    for (int j = 0; j < n; j++) {
      if (!visit[j] && low[j] > map[j][u]) {
        low[j] = map[j][u];
      }
    }
  }

  return sum;
}

int main(void) {
  while (cin >> n && n != 0) {
    memset(map, INF, sizeof(map));

    for (int i = 1; i < n; i++) {
      cin >> c >> count;
      int s = c - 'A';
      for (int j = 0; j < count; j++) {
        cin >> d >> len;
        int e = d - 'A';
        map[s][e] = len;
        map[e][s] = len;
      }
    }

    printf("%d\n", prim());
  }

  return 0;
}