Home > libalgo > 最大流 (Sparse Dinic)

最大流 (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 への最大流を求める

実装

#include <bits/stdc++.h>

using flow_type = int;

struct dinic {
    struct edge {
        int src, dst;
        flow_type cap, flow;
        int rev_idx;
        bool is_rev;
    };
    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 it will be added
    // to `g` when `make_graph` is 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, {});
        if (true) {
            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(), false});
                g[v].push_back({v, u, c, c, (int)g[u].size() - 1, true});
            }
        } else {
            for (auto &e : edges) {
                auto uv = e.first;
                int u = uv.first, v = uv.second;
                flow_type c = e.second;
                g[u].push_back({u, v, c, 0, (int)g[v].size(), false});
                g[v].push_back({v, u, c, c, (int)g[u].size() - 1, true});
            }
        }
    }

    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.dst] == -1 && residue(e) != 0) {
                    level[e.dst] = level[v] + 1;
                    que[lst++] = e.dst;
                }
            }
        }
        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.dst] && residue(e) != 0) {
                flow_type aug = augment(e.dst, std::min(lim, residue(e)));
                if (aug == 0) continue;
                e.flow += aug;
                reverse(e).flow -= aug;
                res += aug;
                lim -= aug;
            }
        }
        return res;
    }

    flow_type residue(const edge &e) { return e.cap - e.flow; }

    edge &reverse(const edge &e) { return g[e.dst][e.rev_idx]; }

    // Output current flow by graphviz dot language.
    // Run `dot $filename -o out.png -T png` on shell.
    void show(const std::string &filename = "out.dot") {
        int fst = 0, lst = 0;
        que[lst++] = s;
        level.assign(n, -1);
        level[s] = 0;
        while (fst != lst) {
            int v = que[fst++];
            for (auto &e : g[v]) {
                if (!e.is_rev && level[e.dst] == -1 && e.flow) {
                    level[e.dst] = level[v] + 1;
                    que[lst++] = e.dst;
                }
            }
        }
        std::map<int, std::vector<int>> rank_to_vertices;
        for (int i = 0; i < n; ++i) {
            rank_to_vertices[level[i]].push_back(i);
        }

        std::ostringstream oss;
        oss << "digraph {" << '\n';
        for (int i = 0; i < n; ++i) {
            oss << "\t" << i;
            if (i == s || i == t) {
                oss << " [ peripheries = 2 ]";
            }
            oss << ";\n";
            for (auto &e : g[i]) {
                if (!e.is_rev) {
                    const char *color = e.flow ? "black" : "gray";
                    oss << "\t" << e.src << " -> " << e.dst
                        << "\t[ "
                        << "label = \"" << e.flow << "/" << e.cap << "\", "
                        << "color = \"" << color << "\", "
                        << "fontcolor = \"" << color << "\"];\n";
                }
            }
        }

        for (auto &p : rank_to_vertices) {
            const char *rank = p.first != -1 ? "same" : "sink";
            oss << "\t{ rank = " << rank << "; ";
            for (int v : p.second) {
                if (v != s && v != t) {
                    oss << v << "; ";
                }
            }
            oss << "}\n";
        }
        oss << "\t{ rank = same; " << s << "; }\n";
        oss << "\t{ rank = same; " << t << "; }\n";
        oss << "}\n";

        std::ofstream ofs(filename);
        ofs << oss.str();
    }
};

検証

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

参考文献

隣接行列版 Dinic と同じ