用一个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 2005 int 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); } }