題目鏈接：http://poj.org/problem?id=1789 裸的最小生成樹(shù)，但是題意非常不好理解，就是說(shuō)每一串字符相當(dāng)于一個(gè)點(diǎn)，任意兩個(gè)字符串中不容字符的個(gè)數(shù)相當(dāng)于邊權(quán)，這樣來(lái)建圖求最小生成樹(shù)。還是只會(huì)用kruskal啊。。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 struct edge
9 {
10 int u, v, w;
11 }e[4000000];
12 char data[2001][8];
13 int p[2001];
14 int tot;
15 int cmp(edge a, edge b)
16 {
17 return a.w < b.w;
18 }
19 int find(int x)
20 {
21 return p[x] != x ? p[x] = find(p[x]) : x;
22 }
23 void add(int x, int y, int z)
24 {
25 tot++;
26 e[tot].u = x;
27 e[tot].v = y;
28 e[tot].w = z;
29 }
30 int main()
31 {
32 int r1, r2, sum, n, ans;
33 while (scanf("%d", &n) != EOF)
34 {
35 if (n == 0) break;
36 tot = 0; memset(e, 0, sizeof(e)); ans = 0;
37 for (int i = 0; i < n; i++) p[i] = i;
38 for (int i = 0; i < n; i++) scanf("%s", data[i]);
39 for (int i = 0; i < n; i++)
40 for (int j = 0; j < n; j++)
41 {
42 sum = 0;
43 if (i != j)
44 for (int k = 0; k < 8; k++)
45 if (data[i][k] != data[j][k]) sum++;
46 add(i, j, sum);
47 }
48 sort(e + 1, e + 1 + tot, cmp);
49 for (int i = 1; i <= tot; i++)
50 {
51 r1 = find(e[i].u); r2 = find(e[i].v);
52 if (r1 != r2)
53 {
54 p[r2] = r1;
55 ans += e[i].w;
56 }
57 }
58 printf("The highest possible quality is 1/%d.\n", ans);
59 }
60 return 0;
61
|