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

例如有如下4个编号：

aaaaaaa

baaaaaa

abaaaaa

aabaaaa

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

问题可以转化为最小代价生成树的问题。因为每两个结点之间都有路径，所以是完全图。 

此题的关键是将问题转化为最小生成树的问题。每一个编号为图的一个顶点，顶点与顶点间的编号差即为这条边的权值，题目所要的就是我们求出最小生成树来。这里我用prim算法来求最小生成树。

自己通过的：

#include<cstdio>

#include<cstring>

char ss[2001][8];

int map[2001][2001],d[2001];

bool visit[2001];

int main()

{

int i,j,k,mi,num,tempj,ans,n;

while(scanf("%d",&num) && num)

{

for(i=1;i<=num;i++)

scanf("%s",ss[i]);

ans=0;

for(i=1;i<=num-1;i++)

{

for(j=i+1;j<=num;j++)

{

n=0;

for(k=0;k<=6;k++)

if(ss[i][k]!=ss[j][k])

n++;

map[i][j]=map[j][i]=n;

}

}

memset(d,99,sizeof(d));

for(i=1;i<=num;i++)

{

d[i]=map[1][i];//最初最小生成树的子集只有节点1存在，考察其余节点到该集合的距离

}

memset(visit,0,sizeof(visit));

visit[1]=1;

for(i=1;i<=num-1;i++)

{

mi=999;

for(j=2;j<=num;j++)

{

if(visit[j]==0 && d[j]<mi)

{

tempj=j;

mi=d[j];

}

}

visit[tempj]=1;

for(j=2;j<=num;j++)

if(visit[j]==0 && d[j]>map[tempj][j])//当tempj加入集合后，观察其他节点与新集合距离有所改变，并且这种改变只是由于tempj带来的变化

d[j]=map[tempj][j];

}

for(i=2;i<=num;i++)

ans+=d[i];

printf("The highest possible quality is 1/%d.\n",ans);

}

return 1;

}

mst1789