水题。。。
题目大意：
用一个7位的字符串代表一个编号，两个编号之间的distance代表这两个编号之间不同字母的个数。一个编号只能由另一个编号“衍生”出来，代价是这两个编号之间相应的distance，现在要找出一个“衍生”方案，使得总代价最小，也就是distance之和最小。
很容易想到，将每两个顶点间的distance求出作为边权，将题目转化为最小生成树问题。由于是稠密图，所以用prim算法。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int i,j,k,n,m,x,a[][],ans,minn,d[],tot,c[];
bool b[];
char s[][];
int main()
{
scanf("%d",&n);
while(n){
memset(d,,sizeof(d));
memset(b,,sizeof(b));
memset(a,,sizeof(a));
ans=;tot=;
for(i=;i<=n;i++)scanf("%s",s[i]);
for(i=;i<n;i++)
for(j=i+;j<=n;j++){
for(k=;k<;k++)if(s[i][k]!=s[j][k])a[i][j]++;
a[j][i]=a[i][j];
}
c[]=;d[]=;k=;b[]=;
while(tot<n){
minn=;
for(i=;i<=n;i++)
if(!b[i]){
if(d[c[k]]+a[c[k]][i]<d[i])d[i]=d[c[k]]+a[c[k]][i];
if(d[i]<minn){
minn=d[i];
x=i;
}
}
b[x]=;
c[++tot]=x;
ans+=d[x];
d[x]=;
k++;
}
printf("The highest possible quality is 1/%d.\n",ans);
scanf("%d",&n);
}
return ;
}