问题:
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 }