ホーム > libalgo

2部グラフの最大マッチング

概要

2部グラフの最大マッチングを最大流のアルゴリズムで求める。

計算量

$O(f(N+M))$ ($f$ は最大マッチングの数で高々 $N$)

使い方

  • 走らせてみると計算量に対して結構速い
  • DAG の最小パス被覆を求めるのにも使える
    • まず頂点 $u$ を $u$, $u+|V|$ に増殖させて $2|V|$ 頂点のグラフを作る
    • 元のグラフに辺 $(u,v)$ が存在するなら辺 $(u,v+|V|)$ を張る
    • このグラフで最大マッチング求め,増殖させたのを戻すとパスになる
    • 最小パス数は $|V|$ - 最大マッチング
bipartite_matching bm(n)
頂点数 n で構築
bm.add_edge(s,t)
s から t に辺をはる
bm.maximum_matching()
最大マッチングを求める
bm.match[u]
頂点 u の相手 (maximum_matching の実行後のみ有効)

実装

class bipartite_matching {
public:
    int n;
    std::vector<std::vector<int>> g;
    std::vector<int> match;

    bipartite_matching(int n_) : n(n_), g(n_), match(n_), used(n_) {}

    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int maximum_matching(void) {
        int res = 0;
        fill(begin(match), end(match), -1);
        for (int v = 0; v < n; ++v) {
            if (match[v] == -1) {
                fill(begin(used), end(used), false);
                if (dfs(v)) res++;
            }
        }
        return res;
    }

private:
    std::vector<int> used;
    bool dfs(int v) {
        used[v] = true;
        for (int u : g[v]) {
            int w = match[u];
            if (w == -1 || (!used[w] && dfs(w))) {
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
        return false;
    }
};

検証

AOJ2251 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2019938

参考文献

蟻本