Truck History

题意大概是这样的：用一个7位的string代表一个编号，两个编号之间的distance代表这两个编号之间不同字母的个数。一个编号只能由另一个编号“衍生”出来，代价是这两个编号之间相应的distance，现在要找出一个“衍生”方案，使得总代价最小，也就是distance之和最小。

题解：问题可以转化为最小代价生成树的问题。因为每两个结点之间都有路径，所以是完全图。此题的关键是将问题转化为最小生成树的问题。每一个编号为图的一个顶点，顶点与顶点间的编号差即为这条边的权值，题目所要的就是我们求出最小生成树来。这里我用prim算法来求最小生成树。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #define INF 100000000
 6 using namespace std;
 7 int g[2002][2002];
 8 int sum,n;
 9 int lowcost[2002];
10 struct Node{
11     char ss[7];
12 }node[2002];
13 int juli(Node a,Node b){
14     int count=0;
15     for(int i=0;i<7;i++){
16         if(a.ss[i]!=b.ss[i])
17          count++;
18     }
19     return count;
20 }
21 void prim(int v0){
22     sum=0;
23     for(int i=1;i<=n;i++){
24         lowcost[i]=g[v0][i];
25     }
26     lowcost[v0]=-1;
27     for(int i=1;i<n;i++){
28         int min=INF;
29         int v=-1;
30         for(int j=1;j<=n;j++){
31             if(lowcost[j]!=-1&&lowcost[j]<min){
32              v=j;min=lowcost[j];    
33             }
34         }
35         if(v!=-1){
36             sum+=lowcost[v];
37             lowcost[v]=-1;
38             for(int k=1;k<=n;k++){
39                 if(lowcost[k]!=-1&&g[v][k]<lowcost[k])
40                    lowcost[k]=g[v][k];
41             }
42         }
43     }
44   printf("The highest possible quality is 1/%d.
",sum);    
45 }
46 int main(){
47     while(~scanf("%d",&n)&&n){
48         for(int i=1;i<=n;i++)
49           scanf("%s",node[i].ss);
50         for(int i=1;i<=n;i++)           
51            for(int j=1+i;j<=n;j++){
52                g[i][j]=g[j][i]=juli(node[i],node[j]);
53            }
54         for(int i=1;i<=n;i++)
55            for(int j=1;j<=n;j++)
56               if(i==j)g[i][j]=0;
57               else if(g[i][j]==0)g[i][j]=INF;
58                   
59               prim(1);   
60     }
61 }

View Code