题目大意

用一个7位的string代表一个编号，两个编号之间的distance代表这两个编号之间不同字母的个数。一个编号只能由另一个编号“衍生”出来，代价是这两个编号之间相应的distance，现在要找出一个“衍生”方案，使得总代价最小，也就是distance之和最小。

例如有如下4个编号：

aaaaaaa
baaaaaa
abaaaaa
aabaaaa

显然的，第二，第三和第四编号分别从第一编号衍生出来的代价最小，因为第二，第三和第四编号分别与第一编号只有一个字母是不同的，相应的distance都是1，加起来是3。也就是最小代价为3。

解题思路

此题的关键是将问题转化为最小生成树的问题。因为每两个节点之间都有路径，所以是完全图。每一个编号为图的一个顶点，顶点与顶点间的编号差即为这条边的权值，题目所要的就是我们求出最小生成树来。这里我用克鲁斯卡尔算法来求最小生成树。

#include<iostream>
#include<string>
#include<string.h>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
#pragma warning(disable:4996)#define inf 0x3f3f3f3f
#define ll long long
#define vec vector<int>
#define P pair<int,int>
#define MAX 2005int N, kind[MAX];
char s[MAX][7];struct edge {int u, v, d;edge(int a = 0, int b = 0, int c = 0) { u = a, v = b, d = c; }
};
bool cmp(edge e1, edge e2) { return e1.d < e2.d; }
vector<edge> v;int find(int k) {if (k == kind[k])return k;else return kind[k] = find(kind[k]);
}
void unite(int a, int b) { kind[find(b)] = kind[find(a)]; }int cal(char * s1, char * s2) {int sum = 0;for (int i = 0; i < 7; i++)if (s1[i] != s2[i])sum++;return sum;
}
int main() {while (scanf("%d",&N) && N) {v.clear();for (int i = 1; i <= N; i++)scanf("%s",&s[i]), kind[i] = i;for (int i = 1; i <= N; i++)for (int j = i + 1; j <= N; j++)v.push_back(edge(i, j, cal(s[i], s[j])));sort(v.begin(), v.end(), cmp);int res = 0, cnt = 0;for (int i = 0; i < v.size() && cnt < N - 1; i++) {edge e = v[i];if (find(e.u) != find(e.v)) {unite(e.u, e.v);res += e.d; cnt++;}}printf("The highest possible quality is 1/%d.\n", res);}
}