Dinic
(Data_structure/Dinic.hpp)

• View this file on GitHub
• Last update: 2023-09-16 04:04:22+00:00
• Include: #include "Data_structure/Dinic.hpp"

コンストラクタ

Dinic<Cap> dinic(int N)

• $N$頂点のグラフを作成する．何も辺が存在しない．
• Cap は long long もしくは int であること．

add_edge

int add_edge(int from, int to, Cap cap)

• fromからtoへ容量capの辺を追加する。
• 以降、追加した辺の本数を $M$ とする。
• 追加した辺の番号を返す。

制約

• $0 \leq from, to < N$
• $0 \leq cap$

計算量

• (ならし？) $O(1)$

flow

(1) Cap flow(int s, int t)
(2) Cap flow(int s, int t, Cap flow_limit)

• (1): s から t まで、上限なしの最大流を求める。
• (2): s から t まで、流量の上限を flow_limit とした最大流を求める。

制約

• $0 \leq s, t < N$
• $s \neq t$
• (2): $0 \leq flow_limit$

計算量

• $O(\min(N^{\frac{2}{3}}M, M^{\frac{3}{2}}))$ (辺の容量がすべて $1$ の場合)
• $O(N^2M)$

min_cut

vector<bool> min_cut(int s)

• max_flow(s, t) を呼んだ後に呼ぶことを想定。頂点 $s$ から到達可能な頂点を true とした vector を返す。

制約

• $0 \leq s < N$

計算量

• $O(N + M)$

get_flow

Cap get_flow(int idx)

• max_flow(s, t) を呼んだ後に呼ぶことを想定。頂点 from から頂点 to へ流れた流量を返す。
• idx は追加された辺の番号である。

制約

• $0 \leq from, to < N$

計算量

• $O(1)$

change_edge

void change_edge(int idx, Cap new_cap, Cap new_flow)

• idx 番目の辺の容量を new_cap に変更し、流量を new_flow に変更する。

制約

• $0 \leq idx < M$

計算量

• $O(1)$

Verified with

• Test/yosupo-Matching-on-Bipartite-Graph.test.cpp

Code

template<class Cap> struct Dinic {
  public:
    Dinic(int n) : n(n), g(n) {}

    int add_edge(int from, int to, Cap cap) {
        int m = (int)edges.size();
        edges.push_back({from, (int)g[from].size()});
        int from_id = (int)g[from].size();
        int to_id = (int)g[to].size();
        if (from == to) to_id++;
        g[from].push_back(dinic_edge{to, to_id, cap});
        g[to].push_back(dinic_edge{from, from_id, 0});
        return m;
    }

    void change_edge(int i, Cap new_cap, Cap new_flow) {
        auto& e = g[edges[i].first][edges[i].second];
        auto& re = g[e.to][e.rev];
        e.cap = new_cap - new_flow;
        re.cap = new_flow;
    }

    Cap flow(int s, int t) {
        return flow(s, t, std::numeric_limits<Cap>::max());
    }

    Cap flow(int s, int t, Cap flow_limit) {
        std::vector<int> level(n), iter(n);
        simple_queue<int> que;

        auto bfs = [&]() {
            std::fill(level.begin(), level.end(), -1);
            level[s] = 0;
            que.clear();
            que.push(s);
            while (!que.empty()) {
                int v = que.pop_front();
                for (auto e : g[v]) {
                    if (e.cap > 0 && level[e.to] == -1) {
                        level[e.to] = level[v] + 1;
                        if (e.to == t) return;
                        que.push(e.to);
                    }
                }
            }
        };

        auto dfs = [&](auto dfs, int v, Cap limit) -> Cap {
            if (v == s) return limit;
            Cap res = 0;
            int level_v = level[v];
            for (int& i = iter[v]; i < int(g[v].size()); i++) {
                dinic_edge& e = g[v][i];
                if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
                Cap d = dfs(dfs, e.to, std::min(limit - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == limit) return res;
            }
            level[v] = n;
            return res;
        };

        Cap flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (level[t] == -1) break;
            std::fill(iter.begin(), iter.end(), 0);
            Cap f = dfs(dfs, t, flow_limit - flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    Cap get_flow(int i) {
        auto _e = g[edges[i].first][edges[i].second];
        auto _re = g[_e.to][_e.rev];
        return _re.cap;
    } 

    std::vector<bool> min_cut(int s) {
        std::vector<bool> visited(n);
        simple_queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int p = que.pop_front();
            visited[p] = true;
            for (auto e : g[p]) {
                if (e.cap && !visited[e.to]) {
                    visited[e.to] = true;
                    que.push(e.to);
                }
            }
        }
        return visited;
    }

  private: 
    int n;
    struct dinic_edge {
        int to, rev;
        Cap cap;
    };
    template<class T> struct simple_queue {
        std::vector<T> data;
        int pos = 0;
        void clear() {
            data.clear();
            pos = 0;
        }
        void push(T val) {
            data.emplace_back(val);
        }
        T pop_front() {
            return data[pos++];
        }
        bool empty() {
            return pos == (int)data.size();
        }
    };
    std::vector<std::pair<int, int>> edges;
    std::vector<std::vector<dinic_edge>> g;
};

#line 1 "Data_structure/Dinic.hpp"
template<class Cap> struct Dinic {
  public:
    Dinic(int n) : n(n), g(n) {}

    int add_edge(int from, int to, Cap cap) {
        int m = (int)edges.size();
        edges.push_back({from, (int)g[from].size()});
        int from_id = (int)g[from].size();
        int to_id = (int)g[to].size();
        if (from == to) to_id++;
        g[from].push_back(dinic_edge{to, to_id, cap});
        g[to].push_back(dinic_edge{from, from_id, 0});
        return m;
    }

    void change_edge(int i, Cap new_cap, Cap new_flow) {
        auto& e = g[edges[i].first][edges[i].second];
        auto& re = g[e.to][e.rev];
        e.cap = new_cap - new_flow;
        re.cap = new_flow;
    }

    Cap flow(int s, int t) {
        return flow(s, t, std::numeric_limits<Cap>::max());
    }

    Cap flow(int s, int t, Cap flow_limit) {
        std::vector<int> level(n), iter(n);
        simple_queue<int> que;

        auto bfs = [&]() {
            std::fill(level.begin(), level.end(), -1);
            level[s] = 0;
            que.clear();
            que.push(s);
            while (!que.empty()) {
                int v = que.pop_front();
                for (auto e : g[v]) {
                    if (e.cap > 0 && level[e.to] == -1) {
                        level[e.to] = level[v] + 1;
                        if (e.to == t) return;
                        que.push(e.to);
                    }
                }
            }
        };

        auto dfs = [&](auto dfs, int v, Cap limit) -> Cap {
            if (v == s) return limit;
            Cap res = 0;
            int level_v = level[v];
            for (int& i = iter[v]; i < int(g[v].size()); i++) {
                dinic_edge& e = g[v][i];
                if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
                Cap d = dfs(dfs, e.to, std::min(limit - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == limit) return res;
            }
            level[v] = n;
            return res;
        };

        Cap flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (level[t] == -1) break;
            std::fill(iter.begin(), iter.end(), 0);
            Cap f = dfs(dfs, t, flow_limit - flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    Cap get_flow(int i) {
        auto _e = g[edges[i].first][edges[i].second];
        auto _re = g[_e.to][_e.rev];
        return _re.cap;
    } 

    std::vector<bool> min_cut(int s) {
        std::vector<bool> visited(n);
        simple_queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int p = que.pop_front();
            visited[p] = true;
            for (auto e : g[p]) {
                if (e.cap && !visited[e.to]) {
                    visited[e.to] = true;
                    que.push(e.to);
                }
            }
        }
        return visited;
    }

  private: 
    int n;
    struct dinic_edge {
        int to, rev;
        Cap cap;
    };
    template<class T> struct simple_queue {
        std::vector<T> data;
        int pos = 0;
        void clear() {
            data.clear();
            pos = 0;
        }
        void push(T val) {
            data.emplace_back(val);
        }
        T pop_front() {
            return data[pos++];
        }
        bool empty() {
            return pos == (int)data.size();
        }
    };
    std::vector<std::pair<int, int>> edges;
    std::vector<std::vector<dinic_edge>> g;
};

Back to top page