POJ 3522 - Slim Span

http://poj.org/problem?id=3522

概要

ノード数 n，エッジ数 m の重みつき無向グラフが与えられるので，その全域木のうち slimness が最小であるものを答える．

slimness とは，その全域木のエッジの重さの最大値と最小値の差とする．

制約

• 2 <= n <= 100
• 0 <= m <= n*(n-1)/2

解法

あるエッジの重み w を選んで，重さが w 以上のエッジのみを選ぶようにして最小全域木を求めると，重さの最小が w な slimness が最小な全域木を求めることができる．

よって，すべての w に対して最小全域木を求めて最小値をとればいい．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct DisjointSet/*{{{*/
 7 {
 8   vector<int> parent;
 9 
10   int root(int x)
11   {
12     if (parent[x] < 0) {
13       return x;
14     } else {
15       parent[x] = root(parent[x]);
16       return parent[x];
17     }
18   }
19 
20   explicit DisjointSet(int n) : parent(n, -1) {}
21 
22   bool unite(int x, int y)
23   {
24     const int a = root(x);
25     const int b = root(y);
26     if (a != b) {
27       if (parent[a] < parent[b]) {
28         parent[a] += parent[b];
29         parent[b] = a;
30       } else {
31         parent[b] += parent[a];
32         parent[a] = b;
33       }
34       return true;
35     } else {
36       return false;
37     }
38   }
39 
40   bool find(int x, int y) { return root(x) == root(y); }
41   int size(int x) { return -parent[root(x)]; }
42 };/*}}}*/
43 
44 struct edge {/*{{{*/
45   int u, v;
46   int w;
47   edge() {}
48   bool operator<(const edge& that) const { return w < that.w; }
49 };/*}}}*/
50 
51 pair<bool,int> kruskal(const vector<edge>& edges, int N, int M)/*{{{*/
52 {
53   DisjointSet s(N);
54   int a = 0;
55   for (vector<edge>::const_iterator it = edges.begin(); it != edges.end() && s.size(0) < N; ++it) {
56     if (it->w >= M && s.unite(it->u, it->v)) {
57       a = max(a, it->w);
58     }
59   }
60   return make_pair(s.size(0) == N, a);
61 }/*}}}*/
62 
63 int main()
64 {
65   int N, M;
66   while (scanf("%d %d", &N, &M) != EOF && N != 0) {
67     vector<edge> es(M);
68     for (int i = 0; i < M; i++) {
69       scanf("%d %d %d", &es[i].u, &es[i].v, &es[i].w);
70       --es[i].u;  --es[i].v;
71     }
72     sort(es.begin(), es.end());
73     static const int INF = 10000000;
74     int ans = INF;
75     for (int i = 0; i < M; i++) {
76       const pair<bool,int> r = kruskal(es, N, es[i].w);
77       if (r.first) {
78         ans = min(ans, r.second - es[i].w);
79       }
80     }
81     if (ans == INF) {
82       puts("-1");
83     } else {
84       printf("%d\n", ans);
85     }
86   }
87   return 0;
88 }