POJ1789Truck History

题意：说实话，题意我没看懂，后来让人给我讲的样例。。。。。

aaaaaaa

baaaaaa

abaaaaa

aabaaaa

这个样例的话，就是输入n下面n行，每行7个字母，让你依次选两行进行比较，不同的有多少个，所以题目中给的样例，1,2行一个不同的，1,3行一个不同的，1,4行一个不同的，所以距离是3，2,3行两个不同的，2,1行一个不同的，2,4行两个不同的，距离是4，这样找下去，可以构成一个无向图，找最小生成树。

解题思路：其实就是一个转化问题，将给的字符串转化成距离的二维数组再找最小生成树即可

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 const int inf = 1 << 29 ;
 7 const int maxn = 2015;
 8 int vis[maxn];
 9 int low[maxn];
10 int dis[maxn][maxn];
11 char ch[maxn][maxn];
12 int i,j,k,n;
13 int sum ;
14 int prim()
15 {
16     int ans = 0, i, j, flag=0, min;
17     memset(vis,0,sizeof(vis));
18     for(i = 1; i <= n; i++)
19     {
20         low[i] = dis[1][i];
21     }
22     //low[1]=0;
23     //vis[1] = 1;
24     for(i = 1; i <= n; i++)
25     {
26         min = inf;
27         flag = 0;
28         for(j = 1; j <= n; j++)
29         {
30             if(min > low[j] && !vis[j])
31             {
32                 min = low[j];
33                 flag = j;
34             }
35         }
36         ans += min;
37         vis[flag] = 1;
38         for(j = 1; j <= n; j++)
39         {
40             if(dis[flag][j] < low[j] && !vis[j])
41             {
42                 low[j] = dis[flag][j];
43             }
44         }
45     }
46     return ans;
47 }
48 int main()
49 {
50     while(cin>>n&&n)
51     {
52         for(i = 1 ; i <= n ; i++)
53         cin>>ch[i] ;
54         for(i = 1;  i <= n ; i++)
55         {
56             for(j = 1 ; j <= n ; j++)
57             {
58                 sum = 0;
59                 for(k = 0; k < 7 ; k++)
60                 {
61                     if(ch[i][k] != ch[j][k])
62                     sum++;
63                 }
64                 dis[i][j] = dis[j][i] = sum;
65             }
66         }
67         cout<<"The highest possible quality is 1/"<<prim()<<"."<<endl;
68     }
69     return 0 ;
70 }

View Code