Dinic's Algorithm
(flow/dinic.hpp)

• View this file on GitHub
• Last update: 2024-01-08 01:08:59+09:00
• Include: #include "flow/dinic.hpp"

Description

Dinic のアルゴリズムは，フローネットワークの最大流を求めるアルゴリズムである．始点からの最短距離を BFS で計算し，残余グラフの増加パスを DFS で見つけ，そのパスにフローを流すことを繰り返す．

Operations

• Dinic(int n)
  • グラフを $n$ 頂点で初期化する
  • 時間計算量: $O(n)$
• void add_edge(int u, int v, T cap)
  • 容量 $cap$ の辺 $(u, v)$ を追加する
  • 時間計算量: $O(1)$
• T max_flow(int s, int t)
  • 始点 $s$ から終点 $t$ への最大流を求める
  • 時間計算量: $O(V^2E)$

Reference

• Dinic 法とその時間計算量 - みさわめも

Verified with

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

Code

#pragma once
#include <algorithm>
#include <limits>
#include <queue>
#include <set>
#include <stack>
#include <vector>

template <typename T>
class Dinic {
   public:
    Dinic() = default;
    explicit Dinic(int V) : G(V), level(V), iter(V) {}

    void add_edge(int u, int v, T cap) {
        G[u].push_back({v, (int)G[v].size(), cap});
        G[v].push_back({u, (int)G[u].size() - 1, 0});
    }

    T max_flow(int s, int t) {
        T flow = 0;
        while (bfs(s, t)) {
            std::ranges::fill(iter, 0);
            T f = 0;
            while ((f = dfs(s, t, INF)) > 0) flow += f;
        }
        return flow;
    }

    std::set<int> min_cut(int s) {
        std::stack<int> st;
        std::set<int> visited;
        st.push(s);
        visited.insert(s);
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            for (auto& e : G[v]) {
                if (e.cap > 0 && !visited.contains(e.to)) {
                    visited.insert(e.to);
                    st.push(e.to);
                }
            }
        }
        return visited;
    }

   private:
    struct Edge {
        int to, rev;
        T cap;
    };

    static constexpr T INF = std::numeric_limits<T>::max() / 2;

    std::vector<std::vector<Edge>> G;
    std::vector<int> level, iter;

    bool bfs(int s, int t) {
        std::ranges::fill(level, -1);
        level[s] = 0;
        std::queue<int> q;
        q.push(s);
        while (!q.empty() && level[t] == -1) {
            int v = q.front();
            q.pop();
            for (auto& e : G[v]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    T dfs(int v, int t, T f) {
        if (v == t) return f;
        for (int& i = iter[v]; i < (int)G[v].size(); ++i) {
            Edge& e = G[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                T d = dfs(e.to, t, std::min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
};

#line 2 "flow/dinic.hpp"
#include <algorithm>
#include <limits>
#include <queue>
#include <set>
#include <stack>
#include <vector>

template <typename T>
class Dinic {
   public:
    Dinic() = default;
    explicit Dinic(int V) : G(V), level(V), iter(V) {}

    void add_edge(int u, int v, T cap) {
        G[u].push_back({v, (int)G[v].size(), cap});
        G[v].push_back({u, (int)G[u].size() - 1, 0});
    }

    T max_flow(int s, int t) {
        T flow = 0;
        while (bfs(s, t)) {
            std::ranges::fill(iter, 0);
            T f = 0;
            while ((f = dfs(s, t, INF)) > 0) flow += f;
        }
        return flow;
    }

    std::set<int> min_cut(int s) {
        std::stack<int> st;
        std::set<int> visited;
        st.push(s);
        visited.insert(s);
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            for (auto& e : G[v]) {
                if (e.cap > 0 && !visited.contains(e.to)) {
                    visited.insert(e.to);
                    st.push(e.to);
                }
            }
        }
        return visited;
    }

   private:
    struct Edge {
        int to, rev;
        T cap;
    };

    static constexpr T INF = std::numeric_limits<T>::max() / 2;

    std::vector<std::vector<Edge>> G;
    std::vector<int> level, iter;

    bool bfs(int s, int t) {
        std::ranges::fill(level, -1);
        level[s] = 0;
        std::queue<int> q;
        q.push(s);
        while (!q.empty() && level[t] == -1) {
            int v = q.front();
            q.pop();
            for (auto& e : G[v]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    T dfs(int v, int t, T f) {
        if (v == t) return f;
        for (int& i = iter[v]; i < (int)G[v].size(); ++i) {
            Edge& e = G[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                T d = dfs(e.to, t, std::min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
};

Back to top page