题目分析：还是最小生成树的问题。可能题目不太好懂，就是每个车有一个7位的编码，把每两个车编码中对应位字母不同的个数叫做这两个编码的长度。因为quality=1/sum(t0,td)，所以只要找到所有编码的继承关系使得形成的树的权值最小即可，即最小生成树。
套模板prim
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<memory.h>
using namespace std;
char M[2100][8];
int lowcost[2100],vis[2100];
int distance(int x,int y)
{
int len=0;
for(int i=0;i<=6;i++)
if(M[x][i]!=M[y][i])
len++;
return len;
}
int prim(int n)
{
int i,j,min,pos=0,ans=0;
memset(vis,0,sizeof(vis));
vis[0]=1;
for(i=1;i<n;i++)
lowcost[i]=distance(pos,i);
for(i=1;i<n;i++)
{
min=1000;
for(j=0;j<n;j++)
if(0==vis[j]&&min>lowcost[j])
{min=lowcost[j];pos=j;}
ans+=min;
vis[pos]=1;
for(j=0;j<n;j++)
if(0==vis[j]&&lowcost[j]>distance(pos,j))
lowcost[j]=distance(pos,j);
}
return ans;
}
int main()
{
int i,n;
while(cin>>n)
{
if(n==0) break;
for(i=0;i<n;i++)
cin>>M[i];
printf("The highest possible quality is 1/%d.\n",prim(n));
}
return 0;
}