POJ 1789 Truck History （最小生成树 Prim）

大意：用一个7位的string代表一个编号，两个编号之间的距离代表这两个编号之间不同字母的个数。一个编号只能由另一个编号变化的来，变化的字母的数量就是这两个编号之间相应的距离，现在要找出一个变化方案，使得总代价最小，也就是距离之和最小。

思路：将每个字符串当成一个节点，求出每个节点之间需要变化的次数为边的权值，用Prim建立最小生成树（稠密图）。

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

Truck History