1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<memory.h> 5 using namespace std; 6 #define INF 100 7 #define maxn 2010 8 int dis[maxn][maxn]; 9 int vis[maxn];10 int d[maxn];11 int n;12 int len;13 char a[maxn][100];14 15 void init()16 {17     memset(dis,0,sizeof(dis));18     memset(vis,0,sizeof(vis));19     memset(d,INF,sizeof(d));20     len = 0;21 }22 23 void makedis()24 {25     init();26     int num;27     for(int i = 1; i < n; i++)28     {29         for(int j = i + 1; j <= n; j++)30         {31             num = 0;32             for(int t = 0; t < 7; t++)33             {34                 if(a[i][t] != a[j][t]) num++;35             }36             dis[i][j] = dis[j][i] = num;37         }38     }39 }40 41 void prim()42 {43     int st = 1;44     int cnt,Min,k;45     vis[st] = 1;46     cnt = 1;47     while(cnt < n)48     {49         Min = INF;50         for(int i = 2; i <= n; i++)51         {52             if(!vis[i] && d[i] > dis[st][i])53                 d[i] = dis[st][i];54             if(!vis[i] && Min > d[i])55             {56                 Min = d[i];57                 k = i;58             }59         }60         vis[k] = 1;61         st = k;62         len += Min;63         cnt++;64     }65 }66 67 int main()68 {69     freopen("input.txt","r",stdin);70     while(scanf("%d",&n) && n)71     {72         for(int i = 1; i <= n; i++)73             scanf("%s",&a[i]);74         makedis();75         prim();76         printf("The highest possible quality is 1/%d.\n",len);77     }78     return 0;79 }80 /*81 482 aaaaaaa83 baaaaaa84 abaaaaa85 aabaaaa86 487 aaaaaaa88 bbaaaaa89 abaaaaa90 aabbaaa91 092 */93 /*输出94 1/395 1/496 */