ホーム > libalgo

最大流 (Sparse Dinic)

概要

グラフを隣接リストで持つ Dinic 法.

計算量

$O(V^2 E)$

使い方

  • 計算量に対して非常に速い
    • ワーストケースではきちんと遅くなる
    • 二部グラフの最大マッチングや全ての辺の容量が等しい場合は速いことが保証される
  • スタックオーバーフローに注意
Dinic dinic(n)
サイズ n のグラフを作る
dinic.add_edge(u,v,c)
u から v へ容量 c の辺を張る
dinic.maximum_flow(s,t)
s から t への最大流を求める

実装

struct Dinic {
public:
    using Flow = int;
    Dinic(int n_) : n(n_), g(n_) {}
    Flow maximum_flow(int s_, int t_) {
        s = s_;
        t = t_;
        que.resize(n);
        Flow res = 0;
        while (levelize()) {
            prog.assign(n, 0);
            res += augment(s, std::numeric_limits<Flow>::max());
        }
        return res;
    }
    void add_edge(int u, int v, Flow c) {
        if (u == v || c == 0) return;
        g[u].push_back({u, v, c, 0, (int)g[v].size()});
        g[v].push_back({v, u, c, c, (int)g[u].size() - 1});
    }

private:
    struct Edge {
        int s, d;
        Flow c, f;
        int r;
    };
    int n, s, t;
    std::vector<std::vector<Edge>> g;
    std::vector<int> level, prog, que;

    bool levelize() {
        int fst = 0, lst = 0;
        que[lst++] = s;
        level.assign(n, -1);
        level[s] = 0;
        while (fst != lst) {
            int v = que[fst++];
            if (v == t) break;
            for (auto &e : g[v]) {
                if (level[e.d] == -1 && residue(e) != 0) {
                    level[e.d] = level[v] + 1;
                    que[lst++] = e.d;
                }
            }
        }
        return level[t] != -1;
    }
    Flow augment(int v, Flow lim) {
        Flow res = 0;
        if (v == t) return lim;
        for (int &i = prog[v]; i < (int)g[v].size(); ++i) {
            if (lim == 0) break;
            auto &e = g[v][i];
            if (level[v] < level[e.d] && residue(e) != 0) {
                Flow aug = augment(e.d, std::min(lim, residue(e)));
                if (aug == 0) continue;
                e.f += aug;
                reverse(e).f -= aug;
                res += aug;
                lim -= aug;
            }
        }
        return res;
    }
    Flow residue(const Edge &e) { return e.c - e.f; }
    Edge &reverse(const Edge &e) { return g[e.d][e.r]; }
};

検証

AOJ GLP6A http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2017704

参考文献

隣接行列版 Dinic と同じ