大意：用一个7位的string代表一个编号，两个编号之间的距离代表这两个编号之间不同字母的个数。一个编号只能由另一个编号变化的来，变化的字母的数量就是这两个编号之间相应的距离，现在要找出一个变化方案，使得总代价最小，也就是距离之和最小。
思路：将每个字符串当成一个节点，求出每个节点之间需要变化的次数为边的权值，用Prim建立最小生成树（稠密图）。
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
int Map[2010][2010];
char s[2010][8];
int dis[2010];
int n;
int min(int a, int b)
{
return a > b ? b : a;
}
int length(int i, int j)
{
int cnt = 0;
for(int k = 0; k < 7; k++)
{
if(s[i][k] != s[j][k])
cnt++;
}
return cnt;
}
int Prim()
{
int Ans;
int Min_ele, Min_node;
memset(dis, INF, sizeof(dis));
Ans = 0;
int r = 1;
for(int i = 1; i <= n-1; i++)
{
Min_ele = INF;
dis[r] = -1;
for(int j = 1; j <= n; j++)
{
if(dis[j] >= 0)
{
dis[j] = min(dis[j], Map[r][j]);
if(dis[j] < Min_ele)
{
Min_ele = dis[j];
Min_node = j;
}
}
}
r = Min_node;
Ans += Min_ele;
}
return Ans;
}
void Solve()
{
while(~scanf("%d%*c", &n) && n)
{
for(int i = 1; i <= n; i++)
{
scanf("%s", s[i]);
}
memset(Map, 0, sizeof(Map));
for(int i = 1; i <= n-1; i++)
{
for(int j = i+1; j <= n; j++)
{
Map[i][j] = Map[j][i] = length(i, j);
}
}
printf("The highest possible quality is 1/%d.\n", Prim());
}
}
int main()
{
Solve();
return 0;
}