Truck History(prim)

读不懂题再简单也不会做，英语是硬伤到哪都是真理，sad++。

此题就是一个最小生成树，两点之间的权值是毎两串之间的不同字母数。

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int N=2020;
 4 const int INF=1<<28;
 5 int map[N][N],vis[N],dis[N];
 6 int n,sum;
 7 void prim()
 8 {
 9     int pos;
10     for (int i = 1; i <= n; i ++)
11     {
12         dis[i] = map[1][i];
13     }
14     vis[1] = 1;
15     for (int i = 1; i <= n-1; i ++)
16     {
17         int min = INF;
18         for (int j = 1; j <= n; j ++)
19         {
20             if (!vis[j] && dis[j] < min)
21             {
22                 min = dis[j];
23                 pos = j;
24             }
25         }
26         sum += min;
27         vis[pos] = 1;
28         for (int j = 1; j <= n; j ++)
29         {
30             if (!vis[j] && dis[j] > map[pos][j])
31                 dis[j] = map[pos][j];
32         }
33 
34     }
35 }
36 void init()
37 {
38     sum = 0;
39     for (int i = 0; i <= n; i ++)
40     {
41         for (int j = 0; j <= n; j ++)
42         {
43             map[i][j]  = INF;
44         }
45         map[i][i] = 0;
46         vis[i] = 0;
47     }
48 
49 }
50 int main()
51 {
52     char str[N][12];
53     int cnt;
54     while(~scanf("%d",&n)&&n)
55     {
56 
57         init();
58         for (int i = 1; i <= n; i ++)
59         {
60             scanf("%s",str[i]+1);
61         }
62         for (int i = 1; i <= n; i ++)
63         {
64             for (int j = i+1; j <= n; j ++)
65             {
66                 cnt = 0;
67                 for (int k = 1; k <= 7; k ++)
68                 {
69                     if (str[i][k]!=str[j][k])
70                         cnt++;
71                 }
72                 map[i][j] = cnt;
73                 map[j][i] = cnt;
74             }
75         }
76         prim();
77         printf("The highest possible quality is 1/%d.
",sum);
78     }
79     return 0;
80 
81 }

View Code