poj 1789 Truck History

 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 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 */