最大流 (Dinic)

概要

Dinic のアルゴリズムはグラフの最大流を求める． Edmonds-Kerp のように残余グラフで最短距離を求めた後，距離が増加する向きの辺のみを使って流せるだけ流す．流せなくなったら最短経路を求めなおしてまた流す．これをそれ以上流せなくなるまで続ける．参考文献のスライドで紙芝居になっているのでそれを見ると一発で分かるかも．

DFS がどこまで進んだかを覚えておかないと (下の実装では vector<int> prog) 計算量レベルで遅くなるので注意が必要．また，蟻本では最短経路を求めた後 1 つの道に沿って流せた時点で終了し，最短経路を求めなおしているが，そこで諦めずに経路が存在しなくなるまで流すほうが速くなる．さらに BFS を逆側から行ったりリンクカットツリーを使うことでさらに速くできる．詳しくは参考文献のみさんわさんの記事を参照．

計算量

$O(V^2 E + V^2)$ 追加 $V^2$ は隣接リストの構築．

使い方

using Flow = int し Edge 構造体に Flow cap というメンバを追加する
走らせてみると計算量に対して非常に速いが，ワーストケースではきちんと遅くなる
二部グラフの最大マッチングや全ての辺の容量が等しい場合は速いことが保証される．

dinic dn(g): グラフ g を組み込む
dn.solve(s,t): s から t への最大流を求める
dn.flow[u][v]: 辺 (u, v) の流量 (solve の実行後にのみ有効)

実装

struct dinic {
    int n, s, t;
    std::vector<int> level, prog, que;
    std::vector<std::vector<Flow>> cap, flow;
    std::vector<std::vector<int>> g;
    Flow inf;
    dinic(const Graph &graph)
        : n(graph.size()),
          cap(n, std::vector<Flow>(n)),
          flow(n, std::vector<Flow>(n)),
          g(n, std::vector<int>()),
          inf(std::numeric_limits<Flow>::max() / 8) {
        for (int i = 0; i < n; i++) {
            for (auto &e : graph[i]) {
                int u = e.src, v = e.dst;
                Flow c = e.cap;
                cap[u][v] += c;
                cap[v][u] += c;
                flow[v][u] += c;
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
    }
    inline Flow residue(int u, int v) { return cap[u][v] - flow[u][v]; }
    Flow solve(int s_, int t_) {
        this->t = t_, this->s = s_;
        que.resize(n + 1);
        Flow res = 0;
        while (levelize()) {
            prog.assign(n, 0);
            res += augment(s, inf);
        }
        return res;
    }
    bool levelize() {
        int l = 0, r = 0;
        level.assign(n, -1);
        level[s] = 0;
        que[r++] = s;
        while (l != r) {
            int v = que[l++];
            if (v == t) break;
            for (const int &d : g[v])
                if (level[d] == -1 && residue(v, d) != 0) {
                    level[d] = level[v] + 1;
                    que[r++] = 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++) {
            const int &d = g[v][i];
            if (residue(v, d) == 0 || level[v] >= level[d]) continue;
            const Flow aug = augment(d, std::min(lim, residue(v, d)));
            flow[v][d] += aug;
            flow[d][v] -= aug;
            res += aug;
            lim -= aug;
            if (lim == 0) break;
        }
        return res;
    }
};

検証

AOJ GLP6A (Submission)