poj 1789

题目可能有点难读懂，copy一下别人的讲解，这个题还是个简单的最小生成树。

题意：用一个7位的字符串代表一个编号，这两个编号之间不同字母的个数等于两个编号之间的距离。一个编号只能由另一个编号“衍生”出来，代价是这两个编号之间相应的distance，现在要找出一个“衍生”方案，使得总代价最小，也就是distance之和最小。
案例说明：
1.aaaaaaa
2.baaaaaa
3.abaaaaa
4.aabaaaa
1和2,3,4之间的距离都为1,2和3的距离为2,2和4的距离为2,3和4的距离为2.
显然的，第二，第三和第四编号分别从第一编号衍生出来的代价最小，因为第二，第三和第四编号分别与第一编号只有一个字母是不同的，相应的distance都是1，加起来是3。也就是最小代价为3。
问题可以转化为最小代价生成树的问题。

#include <cstdio>
#include <cstring>
#include <iostream>
#define MAX 2010

using namespace std;
int n;
char str[MAX][8];
int map[MAX][MAX];
int low[MAX];
int visit[MAX];
int prim() {
  memset(visit, 0, sizeof(visit));
  int sum = 0;
  visit[0] = 1;
  for (int i = 0; i < n; i++) {
    if (visit[i])
      continue;
    low[i] = map[0][i];
  }
  for (int i = 0; i < n - 1; i++) {
    int minn = 0x3f3f3f3f;
    int u;
    for (int j = 0; j < n; j++) {
      if (low[j] < minn && !visit[j]) {
        minn = low[j];
        u = j;
      }
    }
    sum += minn;
    visit[u] = 1;

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

  return sum;
}

int main(int argc, char const *argv[]) {
  while (~scanf("%d", &n) && n) {
    memset(map, 0, sizeof(map));
    for (int i = 0; i < n; i++) {
      scanf("%s", str[i]);
    }

    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        for (int k = 0; k < 7; k++) {
          if (str[i][k] != str[j][k]) {
            map[i][j]++;
            map[j][i] = map[i][j];
          }
        }
      }
    }

    printf("The highest possible quality is 1/%d.\n", prim());
  }
  return 0;
}