Dinic's Algorithm（最大流問題）
(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"

概要

最大流問題 (maximum-flow problem) を解くアルゴリズム． 1970年に Yefim Dinitz が考案した．

同じく最大流問題を解く Ford-Fulkerson algorithm は「DFS で残余グラフ内の増加パスを探し，そこにフローを流す」ということを繰り返すアルゴリズムである． Dinic’s algorithm では，この増加パスを探す部分に対して規則を作り，無闇に探索しない工夫を行っている．

アルゴリズムの流れは次の通り．

BFS により，残余グラフ上における source から各ノードへの増加パスの長さを求める
DFS により，増加パスであり，なおかつ先に求めた長さが狭義単調増加するような sink への経路を探す
発見した増加パスにフローを流せるだけ流し，残余グラフを更新する
候補の経路が無くなるまで手順2, 3を繰り返す
source から sink への増加パスが無くなるまで手順1~4を繰り返す

計算量は，グラフのノード数と辺数をそれぞれ $\lvert V \rvert, \lvert E \rvert$ とすると，$\mathcal{O}(\lvert V \rvert ^2 \lvert E \rvert)$ となる．しかし，大抵の場合は見積りより高速であるとされる．

参考

秋葉拓哉ほか. “高速な最大流アルゴリズム”. プログラミングコンテストチャレンジブック第2版. マイナビ出版, 2012, pp.194-195.
“Dinic’s algorithm”. Wikipedia. https://en.wikipedia.org/wiki/Dinic's_algorithm.
“ディニッツ法”. Wikipedia. https://ja.wikipedia.org/wiki/ディニッツ法.
tanaka-a. “燃やす埋める問題とProject Selection Problemの整理”. Qiita. https://qiita.com/tanaka-a/items/fb8d84c44190c7098047.
“燃やす埋める問題”. いかのたこつぼ. https://ikatakos.com/pot/programming_algorithm/graph_theory/maximum_flow/burn_bury_problem.
“最大流問題について”. https://topcoder-g-hatena-ne-jp.jag-icpc.org/Mi_Sawa/20140311/.
“Dinic 法とその時間計算量”. https://misawa.github.io/others/flow/dinic_time_complexity.html.

問題

“D - Maxflow”. AtCoder Library Practice Contest. AtCoder. https://atcoder.jp/contests/practice2/tasks/practice2_d.

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

Dinic's Algorithm（最大流問題） (algorithm/Graph/Flow/dinic.hpp)

概要

参考

問題

Verified with

Code

Dinic's Algorithm（最大流問題）
(algorithm/Graph/Flow/dinic.hpp)