ホーム > libalgo

最大流 (Sparse Dinic)

概要

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

計算量

$O(V^2 E)$

使い方

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

実装

using flow_type = int;

struct dinic {
    struct edge {
        int s, d;
        flow_type c, f;
        int r;
    };
    int n, s, t;
    std::vector<std::vector<edge>> g;
    std::vector<int> level, prog, que;
    std::vector<std::pair<std::pair<int, int>, flow_type>> edges;

    dinic(int n_ = 0) : n(n_) {}

    // Compute the maximum-flow from `s_` to `t_` by Dinic's algorithm.
    flow_type maximum_flow(int s_, int t_) {
        s = s_;
        t = t_;
        make_graph();
        que.resize(n);
        flow_type res = 0;
        while (levelize()) {
            prog.assign(n, 0);
            res += augment(s, std::numeric_limits<flow_type>::max());
        }
        return res;
    }

    // Add an edge from `u` to `v` with capacity `c`. Note that the edge will be
    // added to `g` when `make_graph` was called instead of just after calling
    // this function.
    void add_edge(int u, int v, flow_type c) {
        if (u != v && c != 0) {
            edges.emplace_back(std::make_pair(u, v), c);
        }
    }

    void make_graph() {
        g.assign(n, {});
        std::sort(edges.begin(), edges.end());
        for (auto it = edges.begin(); it != edges.end();) {
            flow_type c = 0;
            auto uv = it->first;
            while (it != edges.end() && it->first == uv) {
                c += it->second;
                ++it;
            }
            int u = uv.first, v = uv.second;
            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});            
        }
    }

    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_type augment(int v, flow_type lim) {
        flow_type 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_type 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_type 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=2454780

参考文献

隣接行列版 Dinic と同じ