最大流 (Sparse Dinic)

#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();
    }
};