竟然一次就过了。。。。真是罕见。。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1789
题意 ：
看ｄｉｓｃｕｓ了。。。。就是每个字符串相同位置，位置不同的，这样，这两个字符串的距离就＋１。最后要求距离和倒数最大，就代表距离最小。所以最小生成树搞 克鲁斯卡尔 ＋ 并查集合
没有变态数据，不过数据量貌似很大啊
1 #include <stdio.h>
2 #include <math.h>
3 #include <algorithm>
4 #define max 2001
5 using namespace std;
6 int m, n, p[max];
7 char input[max][8];
8 struct E{
9 int u, v, w;
10 }e[4000000];
11 int cmp(E a, E b){
12 return a.w > b.w;
13 }
14 int find(int x){
15 if(x != p[x])return p[x] = find(p[x]);
16 return p[x];
17 }
18 int main(){
19 int i, j, u, v, dis, k, c, tc, res;
20 while(scanf("%d", &m), m){
21 c = res = 0;
22 for(i = 0; i < max; i++)
23 p[i] = i;
24 for(i = 1; i <= m; i++)
25 scanf("%s", input[i]);
26 for(i = 1; i <= m; i++){
27 for(j = i + 1; j <= m; j++){
28 dis = 0;
29 if(i != j){
30 for(k = 0; k < 8; k++)
31 if(input[i][k] != input[j][k])dis++;
32 if(dis){
33 // printf("%d -> %d = %d\n", i, j, dis);
34 e[c].u = i;
35 e[c].v = j;
36 e[c++].w = dis;
37 }
38 }
39 }
40 }
41 tc = c;
42 make_heap(e, e + c, cmp);
43 // printf("%d %d %d\n", e[0].u, e[0].v, e[0].w);
44 for(n = 1; n < m; tc--){
45 if(!tc)break;
46 if((u = find(e[0].u)) != (v = find(e[0].v))){
47 p[u] = v;n++;
48 res += e[0].w;
49 }
50 // printf("%d %d %d\n", e[0].u, e[0].v, e[0].w);
51 pop_heap(e, e + tc, cmp);
52 }
53 printf("The highest possible quality is ");
54 if(res)
55 printf("1/%d.\n", res);
56 else puts("0.");
57 }
58 return 0;
59 }