問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1861http://acm.pku.edu.cn/JudgeOnline/problem?id=2485思路:
這里題目并沒有明確要求求最小生成樹，而是要求一顆最長邊最小的生成樹
我們可以證明:
如果T是一顆最小生成樹，那么T所包含的最長邊一定是所有生成樹中最小的，即最小生成樹滿足題目要求
Prove:
如果T的最長邊(x, y)并非最小
那么，存在一顆生成樹R，其最長邊(u, v)<(x, y)，即生成樹R的任何一條邊都小于(x, y)
現在，采用剪切-粘帖的方法來證明T不是一顆最小生成樹，即矛盾
將T中的最長邊(x, y)剪切掉，這樣就得到兩顆子樹
在R中，至少存在一條邊(p, q)可以將這兩顆子樹連接起來，這樣就得到:
T - (x, y) + (p, q) < T
代碼(這里采用Kruskal算法，并查集實現)
1 /* union-find sets, Kruskal algorithm */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_N 1001
6 #define MAX_M 15001
7 struct Edge{
8 int len;
9 int from, to;
10 }edges[MAX_M];
11 int parent[MAX_N], rank[MAX_N];
12 int n, m;
13
14 void
15 make_set()
16 {
17 int i;
18 for(i=1; i<=n; i++)
19 parent[i] = i;
20 memset(rank, 0, sizeof(rank));
21 }
22
23 int
24 find(int x)
25 {
26 int tmp, rt = x;
27 while(parent[rt] != rt)
28 rt = parent[rt];
29 while(x != rt) {
30 tmp = parent[x];
31 parent[x] = rt;
32 x = tmp;
33 }
34 return rt;
35 }
36
37 void
38 Union(int x, int y)
39 {
40 int a = find(x);
41 int b = find(y);
42 if(a == b)
43 return;
44 if(rank[a] > rank[b])
45 parent[b] = a;
46 else {
47 parent[a] = b;
48 if(rank[a] == rank[b])
49 ++rank[b];
50 }
51 }
52
53 int
54 compare(const void *arg1, const void *arg2)
55 {
56 return ((struct Edge *)arg1)->len - ((struct Edge *)arg2)->len;
57 }
58
59 void
60 init()
61 {
62 int i;
63 for(i=0; i<m; i++)
64 scanf("%d %d %d", &edges[i].from, &edges[i].to, &edges[i].len);
65 qsort(edges, m, sizeof(struct Edge), compare);
66 }
67
68 void
69 kruskal()
70 {
71 int i, a, b, count = 0;
72 int mark[MAX_N];
73 make_set();
74 for(i=0; i<m; i++) {
75 a = find(edges[i].from);
76 b = find(edges[i].to);
77 if(a != b) {
78 mark[count++] = i;
79 Union(a, b);
80 }
81 }
82 /* output */
83 printf("%d\n", edges[mark[count-1]].len);
84 printf("%d\n", count);
85 for(i=0; i<count; i++)
86 printf("%d %d\n", edges[mark[i]].from, edges[mark[i]].to);
87 }
88
89 int
90 main(int argc, char **argv)
91 {
92 while(scanf("%d %d", &n, &m) != EOF) {
93 init();
94 kruskal();
95 }
96 }