グラフの最小全域木の構造に関する理解を問う良問ですね。

問題概要

連結な重み付き無向グラフ $G$ が与えられます (頂点数 $N$ 、辺数 $M$ )。

$G$ の全域木のうち、全域木に含まれる $N-1$ 本の辺の重みのメディアンの最小値を求めてください。

制約

$2 \le N \le 1000$
$N-1 \le M \le 10000$
$N$ は偶数

解法

グラフ $G$ の最小全域木の一つを $T$ として、他の任意の全域木を $S$ とします。 $T$ に含まれる辺の重みを小さい順に $t_{1}, \dots, t_{N-1}$ として、 $S$ に含まれる辺の重みを小さい順に $s_{1}, \dots, s_{N-1}$ としましょう。

このとき、

$t_{1} \le s_{1}$
$t_{2} \le s_{2}$
$\dots$
$t_{N-1} \le s_{N-1}$

が成り立つことが知られています。つまり最小全域木は、

$\sum_{i = 1}^{N-1} t_{i} \le \sum_{i = 1}^{N-1} s_{i}$ 　(これは最小全域木の定義です)

を満たすだけでなく、「その全域木に含まれる各辺の重みのうち $k$ 番目に小さな値」についても最小な全域木となっているのです。なお、この性質から、最小全域木 (一般に複数考えられます) に含まれる辺の重みを小さい順にソートして得られる数列が、常に一定であることも従います。

以上の性質の証明については、問題の公式解説に丁寧に記載されていますので、参考にしていただけたらと思います。

また、問題を解くための具体的なアルゴリズムとしては、通常の最小全域木を求める Kruskal 法を適用すればよいでしょう。計算量は $O(N \log M)$ となります。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Union-Find
struct UnionFind {
    vector<int> par;

    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    // 辺数
    int N, M;
    while (cin >> N >> M, N) {
        // 辺を表す構造体
        using pint = pair<int, int>;  // 両端点
        using Edge = pair<long long, pint>;  // (重み, 両端点)
        
        // 入力
        vector<Edge> edges(M);
        for (int i = 0; i < M; ++i) {
            cin >> edges[i].second.first >> edges[i].second.second
                >> edges[i].first;
            --edges[i].second.first;
            --edges[i].second.second;
        }

        // 辺を重み順にソート
        sort(edges.begin(), edges.end());

        // Kruskal 法 
        UnionFind uf(N);
        int num = 0;  // 辺の本数
        long long res = 0;  // 答え
        for (auto e: edges) {
            long long w = e.first;
            int u = e.second.first, v = e.second.second;

            // 辺 (u, v) は追加できない場合
            if (uf.issame(u, v)) continue;

            // 辺 (u, v) を追加するとき
            uf.merge(u, v);
            ++num;

            // メディアンに到達
            if (num == (N + 1) / 2) {
                res = w;
                break;
            }
        }
        cout << res << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2536 Median Tree (JAG 模擬地区 2012 C) (400 点)

問題概要

制約

解法

コード