poj1789Truck History(简单最小生成树）

模板题题意是一个字符串跟一个字符不同的字符串有多少这个数量就相当于权值连起来最小

View Code

 1 #include <iostream>
 2 #include<algorithm>
 3 #include<string.h>
 4 #include<cstdio>
 5 #define INF 0x3f3f3f3f
 6 using namespace std;
 7 char c[2001][10];
 8 int w[2001][2001],vis[2001],low[2001],s;
 9 void prime(int n)
10 {
11     int i,j,k,m;
12     memset(vis,0,sizeof(vis));
13     vis[1] = 1;
14     for(i =2 ; i <= n ; i++)
15     low[i] = w[1][i];
16     for(i = 1; i <= n ; i++)
17     {
18         m = INF;
19         for(j = 1; j <= n ; j++)
20         if(!vis[j]&&low[j]<m)
21         m = low[k=j];
22         if(m==INF)
23         break;
24         s+=m;
25         vis[k] = 1;
26         for(j = 1; j <= n ; j++)
27         if(!vis[j]&&low[j]>w[k][j])
28         low[j] = w[k][j];
29     }
30 }
31 int main()
32 {
33     int i,j,k,n,m,y,x;
34     while(scanf("%d%*c",&n)&&n)
35     {
36         memset(w,INF,sizeof(w));
37         s = 0;
38         for(i = 1; i <= n ; i++)
39         {
40             gets(c[i]);
41         }
42         for(i = 1; i <= n ; i++)
43         {
44             for(j = i+1; j <= n ; j++)
45             {
46                 y = 0;
47                 for(x = 0 ; x < 7 ; x++)
48                 if(c[j][x]!=c[i][x])
49                 y++;
50                 if(w[i][j]>y)
51                 {
52                     w[i][j] = y;
53                     w[j][i] = y;
54                 }
55             }
56         }
57         prime(n);
58         printf("The highest possible quality is 1/%d.\n",s);
59     }
60     return 0;
61 }