飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1158

题意：就是给你n个字母，每个字母由7个字符组成，且都是小写字母，而且不相等，每个字母有一个父亲，且到父亲的距离是跟父亲位置相同字母不同的位置数量，且根节点没有父亲，求距离和最小。

分析：一看，每个节点有个父亲，那么就是一棵树，且距离可以直接定义为父节点到自己点的边长距离，那么要求n-1条边的距离和最小，直接用最小生成树算法即可，我们只要预处理出每对的距离，然后用prim算法即可，因为是稠密图，prim跑得比较优秀，如果是稀疏图，那么直接就kruskal。总体复杂就是，距离n*n*7,prim算法为n*n，所以复杂的为O(n*)n,最后啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=2*1234;
char ch[maxn][10];
int n;
bool vis[maxn];
void init()
{
    for(int i=1; i<=n; i++)scanf("%s",ch[i]+1);
}
short dist[maxn][maxn];
short low[maxn];
void play()
{
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        dist[i][i]=0;
        for(int j=i+1; j<=n; j++)
        {
            int sum=0;
            for(int k=1; k<=7; k++)
            {
                if(ch[i][k]!=ch[j][k])sum++;
            }
            dist[i][j]=dist[j][i]=sum;
        }

    }
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    int pos=1;
    for(int i=2; i<=n; i++)
    {
        low[i]=dist[1][i];
    }

    for(int i=1; i<n; i++)
    {
        int MIN=INF;
        int idx=-1;
        for(int j=1; j<=n; j++)
        {
            if(!vis[j]&&MIN>low[j])
            {
                MIN=low[j];
                idx=j;
            }
        }
        ans+=MIN;
        vis[idx]=1;
        for(int j=1; j<=n; j++)
        {
            if(!vis[j]&&low[j]>dist[idx][j])
            {

                low[j]=dist[idx][j];
            }
        }
    }
    printf("The highest possible quality is 1/%d.\n",ans);
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}