最大流 (Dinic)
(GraphTheory/Dinic.hpp)

• View this file on GitHub
• Last update: 2021-03-16 16:17:21+09:00
• Include: #include "GraphTheory/Dinic.hpp"
• Link: https://tkmst201.github.io/Library/GraphTheory/Dinic.hpp

概要

容量付きの有向グラフにおいて、任意の $2$ 頂点 $s, t$ に対する $s-t$ フローの最大値を求めます。
計算量は、頂点数を $N$ 、辺の数を $M$ として $\mathcal{O}(N^2M)$ です。
より高速で使い勝手の良い AC Library の maxflow を使用したほうが良いです。

• Dinic(int n)
  • $\Theta(n)$ 頂点数 $n$ のグラフで初期化する
• int size()
  • $\Theta(1)$ グラフの頂点数 $N$ を返す
• void add_edge(int u, int v const T & cap)
  • ならし $\Theta(1)$ 頂点 $u$ から頂点 $v$ へ容量 $cap$ の有向辺を張る
• T max_flow(int s, int t)
  • $\mathcal{O}(N^2M)$ $s-t$ フローの最大値を返す

コンストラクタ

Dinic(int n)

頂点数 $n$ のグラフで初期化します。 T には容量の型を指定してください。

制約

• $0 \leq n$
• T は int, unsigned int, long long int, unsigned long long, float, double

計算量

• $\Theta(n)$

---

メンバ関数

以下、頂点数を $N$ 、辺の数を $M$ とします。

---

int size()

グラフの頂点数 $N$ を返します。

計算量

• $\Theta(1)$

---

void add_edge(int u, int v const T & cap)

頂点 $u$ から頂点 $v$ へ容量 $cap$ の有向辺を張ります。

制約

• $0 \leq u, v < N$
• $0 \leq cap$

計算量

• ならし $\Theta(1)$

T max_flow(int s, int t)

$s-t$ フローの最大値を返します。 この関数を $2$ 回以上呼んだ場合の動作は未定義です。

制約

• $0 \leq u, v < N$
• $u \neq v$

計算量

• $\mathcal{O}(N^2M)$

使用例

#include <bits/stdc++.h>
#include "GraphTheory/Dinic.hpp"
using namespace std;

int main() {
	Dinic<int> dinic(5);
	cout << "size() = " << dinic.size() << endl; // 5
	dinic.add_edge(0, 1, 2);
	dinic.add_edge(0, 2, 3);
	dinic.add_edge(1, 2, 2);
	dinic.add_edge(1, 4, 1);
	dinic.add_edge(2, 4, 3);
	cout << "max_flow(0, 4) = " << dinic.max_flow(0, 4) << endl; // 4
}

参考

2020/03/03: http://hos.ac/slides/20150319_flow.pdf
2020/03/03: http://vartkw.hatenablog.com/entry/2016/12/02/002703

Verified with

• Test/Dinic.test.cpp

Code

#ifndef INCLUDE_GUARD_DINIC_HPP
#define INCLUDE_GUARD_DINIC_HPP

#include <vector>
#include <cassert>
#include <queue>
#include <type_traits>
#include <algorithm>
#include <limits>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/Dinic.hpp
 */
template<typename T>
struct Dinic {
	using cap_type = T;
	
private:
	static constexpr cap_type EPS = std::is_floating_point<cap_type>() ? 1e-8 : 0;
	static constexpr cap_type INF = std::numeric_limits<cap_type>::max();
	struct Edge {
		int to, rev;
		cap_type c;
		Edge(int to, int rev, const cap_type & c) : to(to), rev(rev), c(c) {}
	};
	using Graph = std::vector<std::vector<Edge>>;
	Graph g;
	
public:
	Dinic(int n) : g(n) {}
	
	int size() const noexcept {
		return g.size();
	}
	
	void add_edge(int u, int v, const cap_type & cap) {
		assert(0 <= u && u < size());
		assert(0 <= v && v < size());
		assert(cap >= 0);
		g[u].emplace_back(v, g[v].size(), cap);
		g[v].emplace_back(u, g[u].size() - 1, 0);
	}
	
	cap_type max_flow(int s, int t) {
		assert(0 <= s && s < size());
		assert(0 <= t && t < size());
		assert(s != t);
		cap_type res = 0;
		std::vector<int> iter, level;
		while (true) {
			level.assign(size(), -1);
			std::queue<int> que;
			level[s] = 0;
			que.emplace(s);
			while (!que.empty() && level[t] == -1) {
				const int u = que.front();
				que.pop();
				for (const auto & e : g[u]) {
					if (e.c <= EPS || level[e.to] != -1) continue;
					level[e.to] = level[u] + 1;
					if (e.to == t) break;
					que.emplace(e.to);
				}
			}
			if (level[t] == -1) break;
			iter.assign(size(), 0);
			auto dfs = [&](auto self, int u, cap_type f) -> cap_type {
				if (u == t) return f;
				if (level[u] >= level[t]) return 0;
				for (int & i = iter[u]; i < static_cast<int>(g[u].size()); ++i) {
					auto & e = g[u][i];
					if (e.c <= EPS || level[u] >= level[e.to]) continue;
					const cap_type cur = self(self, e.to, std::min(f, e.c));
					if (cur > EPS) {
						e.c -= cur;
						g[e.to][e.rev].c += cur;
						return cur;
					}
				}
				return 0;
			};
			cap_type f;
			while ((f = dfs(dfs, s, INF)) > EPS) res += f;
		}
		return res;
	}
};

#endif // INCLUDE_GUARD_DINIC_HPP

#line 1 "GraphTheory/Dinic.hpp"



#include <vector>
#include <cassert>
#include <queue>
#include <type_traits>
#include <algorithm>
#include <limits>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/Dinic.hpp
 */
template<typename T>
struct Dinic {
	using cap_type = T;
	
private:
	static constexpr cap_type EPS = std::is_floating_point<cap_type>() ? 1e-8 : 0;
	static constexpr cap_type INF = std::numeric_limits<cap_type>::max();
	struct Edge {
		int to, rev;
		cap_type c;
		Edge(int to, int rev, const cap_type & c) : to(to), rev(rev), c(c) {}
	};
	using Graph = std::vector<std::vector<Edge>>;
	Graph g;
	
public:
	Dinic(int n) : g(n) {}
	
	int size() const noexcept {
		return g.size();
	}
	
	void add_edge(int u, int v, const cap_type & cap) {
		assert(0 <= u && u < size());
		assert(0 <= v && v < size());
		assert(cap >= 0);
		g[u].emplace_back(v, g[v].size(), cap);
		g[v].emplace_back(u, g[u].size() - 1, 0);
	}
	
	cap_type max_flow(int s, int t) {
		assert(0 <= s && s < size());
		assert(0 <= t && t < size());
		assert(s != t);
		cap_type res = 0;
		std::vector<int> iter, level;
		while (true) {
			level.assign(size(), -1);
			std::queue<int> que;
			level[s] = 0;
			que.emplace(s);
			while (!que.empty() && level[t] == -1) {
				const int u = que.front();
				que.pop();
				for (const auto & e : g[u]) {
					if (e.c <= EPS || level[e.to] != -1) continue;
					level[e.to] = level[u] + 1;
					if (e.to == t) break;
					que.emplace(e.to);
				}
			}
			if (level[t] == -1) break;
			iter.assign(size(), 0);
			auto dfs = [&](auto self, int u, cap_type f) -> cap_type {
				if (u == t) return f;
				if (level[u] >= level[t]) return 0;
				for (int & i = iter[u]; i < static_cast<int>(g[u].size()); ++i) {
					auto & e = g[u][i];
					if (e.c <= EPS || level[u] >= level[e.to]) continue;
					const cap_type cur = self(self, e.to, std::min(f, e.c));
					if (cur > EPS) {
						e.c -= cur;
						g[e.to][e.rev].c += cur;
						return cur;
					}
				}
				return 0;
			};
			cap_type f;
			while ((f = dfs(dfs, s, INF)) > EPS) res += f;
		}
		return res;
	}
};

Back to top page