algorithm/Graph/Flow/dinic.hpp

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Graph/Flow/dinic.hpp"

Verified with

• verify/aoj-GRL_6_A-dinic.test.cpp

Code

#ifndef ALGORITHM_DINIC_HPP
#define ALGORITHM_DINIC_HPP 1

#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

namespace algorithm {

template <typename Flow>
class Dinic {
public:
    using flow_type = Flow;

private:
    struct Edge {
        int to;         // to:=(行き先ノード).
        flow_type cap;  // cap:=(容量).
        int rev;        // rev:=(逆辺の位置). m_g[to][rev]が逆辺となる．

        explicit Edge(int to, flow_type cap, int rev) : to(to), cap(cap), rev(rev) {}
    };

    int m_vn;                                // m_vn:=(ノード数).
    std::vector<std::vector<Edge>> m_g;      // m_g[v][]:=(ノードvの隣接リスト).
    std::vector<std::pair<int, int>> m_pos;  // m_pos[i]:=(i番目の辺の情報). pair of (from, index).

public:
    Dinic() : Dinic(0) {}
    explicit Dinic(int n) : m_vn(n), m_g(n) {
        assert(n >= 0);
    }
    explicit Dinic(int vn, int en) : Dinic(vn) {
        assert(en >= 0);
        m_pos.reserve(en);
    }

    static constexpr flow_type infinity() { return std::numeric_limits<flow_type>::max(); }
    // ノード数を取得する．
    int order() const { return m_vn; }
    // 辺数を取得する.
    int size() const { return m_pos.size(); }
    // 容量capの有向辺を追加する．
    int add_edge(int from, int to, flow_type cap) {
        assert(0 <= from and from < order());
        assert(0 <= to and to < order());
        assert(cap >= 0);
        int i = m_g[from].size(), j = m_g[to].size();
        if(from == to) ++j;
        m_g[from].emplace_back(to, cap, j);
        m_g[to].emplace_back(from, 0, i);
        m_pos.emplace_back(from, i);
        return size() - 1;
    }
    // ノードsからtへの最大流を求める．O((|V|^2)*|E|).
    flow_type max_flow(int s, int t) { return max_flow(s, t, infinity()); }
    flow_type max_flow(int s, int t, flow_type flow) {
        assert(0 <= s and s < order());
        assert(0 <= t and t < order());
        flow_type res = 0;
        while(res < flow) {
            // (1) BFS: ノードsと各ノード間の増加パスの長さを求める．
            std::vector<int> d(m_vn, -1);  // d[v]:=(ノードs-v間の増加パスの長さ).
            d[s] = 0;
            std::queue<int> que({s});
            while(!que.empty()) {
                int v = que.front();
                que.pop();
                for(const Edge &e : m_g[v]) {
                    if(d[e.to] != -1 or e.cap == 0) continue;
                    d[e.to] = d[v] + 1;
                    que.push(e.to);
                }
            }
            if(d[t] == -1) break;
            // (2) DFS: ノードs-t間の増加パスを探す．
            std::vector<int> next(m_vn, 0);  // next[v]:=(m_g[v][]における次に調べるべき位置).
            auto dfs = [&](auto self, int v, flow_type flow) -> flow_type {
                if(v == t) return flow;
                for(int &i = next[v], end = m_g[v].size(); i < end; ++i) {
                    Edge &e = m_g[v][i];
                    if(d[e.to] <= d[v] or e.cap == 0) continue;
                    flow_type res = self(self, e.to, std::min(flow, e.cap));
                    if(res == 0) continue;
                    e.cap -= res;
                    m_g[e.to][e.rev].cap += res;
                    return res;
                }
                return 0;
            };
            while(res < flow) {
                flow_type tmp = dfs(dfs, s, flow - res);
                if(tmp == 0) break;
                res += tmp;
            }
        }
        return res;
    }
    // i番目の辺の情報を取得する．
    std::tuple<int, int, flow_type, flow_type> get_edge(int i) const {
        assert(0 <= i and i < size());
        const auto &[from, idx] = m_pos[i];
        const Edge &e = m_g[from][idx];
        return {from, e.to, e.cap + m_g[e.to][e.rev].cap, m_g[e.to][e.rev].cap};  // tuple of (from, to, capacity, flow).
    }
    // 最小カットにより，グラフ上のノードを分割する．
    std::vector<bool> min_cut(int s) const {
        assert(0 <= s and s < order());
        std::vector<bool> res(m_vn, false);
        std::queue<int> que({s});
        while(!que.empty()) {
            int v = que.front();
            que.pop();
            if(res[v]) continue;
            res[v] = true;
            for(const Edge &e : m_g[v]) {
                if(!res[e.to] and e.cap > 0) que.push(e.to);
            }
        }
        return res;
    }
    void reset() {
        for(const auto &[from, idx] : m_pos) {
            Edge &e = m_g[from][idx];
            e.cap += m_g[e.to][e.rev].cap;
            m_g[e.to][e.rev].cap = 0;
        }
    }
};

}  // namespace algorithm

#endif

#line 1 "algorithm/Graph/Flow/dinic.hpp"



#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

namespace algorithm {

template <typename Flow>
class Dinic {
public:
    using flow_type = Flow;

private:
    struct Edge {
        int to;         // to:=(行き先ノード).
        flow_type cap;  // cap:=(容量).
        int rev;        // rev:=(逆辺の位置). m_g[to][rev]が逆辺となる．

        explicit Edge(int to, flow_type cap, int rev) : to(to), cap(cap), rev(rev) {}
    };

    int m_vn;                                // m_vn:=(ノード数).
    std::vector<std::vector<Edge>> m_g;      // m_g[v][]:=(ノードvの隣接リスト).
    std::vector<std::pair<int, int>> m_pos;  // m_pos[i]:=(i番目の辺の情報). pair of (from, index).

public:
    Dinic() : Dinic(0) {}
    explicit Dinic(int n) : m_vn(n), m_g(n) {
        assert(n >= 0);
    }
    explicit Dinic(int vn, int en) : Dinic(vn) {
        assert(en >= 0);
        m_pos.reserve(en);
    }

    static constexpr flow_type infinity() { return std::numeric_limits<flow_type>::max(); }
    // ノード数を取得する．
    int order() const { return m_vn; }
    // 辺数を取得する.
    int size() const { return m_pos.size(); }
    // 容量capの有向辺を追加する．
    int add_edge(int from, int to, flow_type cap) {
        assert(0 <= from and from < order());
        assert(0 <= to and to < order());
        assert(cap >= 0);
        int i = m_g[from].size(), j = m_g[to].size();
        if(from == to) ++j;
        m_g[from].emplace_back(to, cap, j);
        m_g[to].emplace_back(from, 0, i);
        m_pos.emplace_back(from, i);
        return size() - 1;
    }
    // ノードsからtへの最大流を求める．O((|V|^2)*|E|).
    flow_type max_flow(int s, int t) { return max_flow(s, t, infinity()); }
    flow_type max_flow(int s, int t, flow_type flow) {
        assert(0 <= s and s < order());
        assert(0 <= t and t < order());
        flow_type res = 0;
        while(res < flow) {
            // (1) BFS: ノードsと各ノード間の増加パスの長さを求める．
            std::vector<int> d(m_vn, -1);  // d[v]:=(ノードs-v間の増加パスの長さ).
            d[s] = 0;
            std::queue<int> que({s});
            while(!que.empty()) {
                int v = que.front();
                que.pop();
                for(const Edge &e : m_g[v]) {
                    if(d[e.to] != -1 or e.cap == 0) continue;
                    d[e.to] = d[v] + 1;
                    que.push(e.to);
                }
            }
            if(d[t] == -1) break;
            // (2) DFS: ノードs-t間の増加パスを探す．
            std::vector<int> next(m_vn, 0);  // next[v]:=(m_g[v][]における次に調べるべき位置).
            auto dfs = [&](auto self, int v, flow_type flow) -> flow_type {
                if(v == t) return flow;
                for(int &i = next[v], end = m_g[v].size(); i < end; ++i) {
                    Edge &e = m_g[v][i];
                    if(d[e.to] <= d[v] or e.cap == 0) continue;
                    flow_type res = self(self, e.to, std::min(flow, e.cap));
                    if(res == 0) continue;
                    e.cap -= res;
                    m_g[e.to][e.rev].cap += res;
                    return res;
                }
                return 0;
            };
            while(res < flow) {
                flow_type tmp = dfs(dfs, s, flow - res);
                if(tmp == 0) break;
                res += tmp;
            }
        }
        return res;
    }
    // i番目の辺の情報を取得する．
    std::tuple<int, int, flow_type, flow_type> get_edge(int i) const {
        assert(0 <= i and i < size());
        const auto &[from, idx] = m_pos[i];
        const Edge &e = m_g[from][idx];
        return {from, e.to, e.cap + m_g[e.to][e.rev].cap, m_g[e.to][e.rev].cap};  // tuple of (from, to, capacity, flow).
    }
    // 最小カットにより，グラフ上のノードを分割する．
    std::vector<bool> min_cut(int s) const {
        assert(0 <= s and s < order());
        std::vector<bool> res(m_vn, false);
        std::queue<int> que({s});
        while(!que.empty()) {
            int v = que.front();
            que.pop();
            if(res[v]) continue;
            res[v] = true;
            for(const Edge &e : m_g[v]) {
                if(!res[e.to] and e.cap > 0) que.push(e.to);
            }
        }
        return res;
    }
    void reset() {
        for(const auto &[from, idx] : m_pos) {
            Edge &e = m_g[from][idx];
            e.cap += m_g[e.to][e.rev].cap;
            m_g[e.to][e.rev].cap = 0;
        }
    }
};

}  // namespace algorithm

Back to top page