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. ",len); 77 } 78 return 0; 79 } 80 /* 81 4 82 aaaaaaa 83 baaaaaa 84 abaaaaa 85 aabaaaa 86 4 87 aaaaaaa 88 bbaaaaa 89 abaaaaa 90 aabbaaa 91 0 92 */ 93 /*输出 94 1/3 95 1/4 96 */