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

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

概要

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

計算量

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

使い方

走らせてみると計算量に対して結構速い

DAG の最小パス被覆を求めるのにも使える

まず頂点 $u$ を $u$, $u+

$ に増殖させて $2

$ 頂点のグラフを作る

元のグラフに辺 $(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

参考文献

蟻本