最大流 (Edmonds-Karp)
(GraphTheory/EdmondsKarp.hpp)

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

概要

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

EdmondsKarp(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}(NM^2)$ $s-t$ フローの最大値を返す

コンストラクタ

EdmondsKarp(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}(NM^2)$

使用例

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

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

参考

2020/02/27: http://hos.ac/slides/20150319_flow.pdf

Verified with

Test/EdmondsKarp.test.cpp

Code

#ifndef INCLUDE_GUARD_EDMONDS_KARP_HPP
#define INCLUDE_GUARD_EDMONDS_KARP_HPP

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

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/EdmondsKarp.hpp
 */
template<typename T>
struct EdmondsKarp {
	using cap_type = T;
	
private:
	static constexpr cap_type EPS = std::is_floating_point<cap_type>() ? 1e-8 : 0;
	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:
	explicit EdmondsKarp(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<std::pair<int, int>> prv(size(), std::make_pair(-1, -1));
		while (true) {
			std::vector<int> visited;
			std::queue<int> que;
			prv[s].first = s;
			visited.emplace_back(s);
			que.emplace(s);
			while (!que.empty() && prv[t].first == -1) {
				const int u = que.front();
				que.pop();
				for (int i = 0; i < static_cast<int>(g[u].size()); ++i) {
					const int to = g[u][i].to;
					if (prv[to].first != -1 || g[u][i].c <= EPS) continue;
					prv[to] = {u, i};
					visited.emplace_back(to);
					if (to == t) break;
					que.emplace(to);
				}
			}
			if (prv[t].first == -1) break;
			cap_type flow = g[prv[t].first][prv[t].second].c;
			for (int u = prv[t].first; u != prv[u].first; u = prv[u].first) {
				flow = std::min(flow, g[prv[u].first][prv[u].second].c);
			}
			for (int u = t; u != prv[u].first; u = prv[u].first) {
				const auto [v, eidx] = prv[u];
				g[v][eidx].c -= flow;
				g[u][g[v][eidx].rev].c += flow;
			}
			for (int u : visited) prv[u] = {-1, -1};
			res += flow;
		}
		return res;
	}
};

#endif // INCLUDE_GUARD_EDMONDS_KARP_HPP

#line 1 "GraphTheory/EdmondsKarp.hpp"



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

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/EdmondsKarp.hpp
 */
template<typename T>
struct EdmondsKarp {
	using cap_type = T;
	
private:
	static constexpr cap_type EPS = std::is_floating_point<cap_type>() ? 1e-8 : 0;
	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:
	explicit EdmondsKarp(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<std::pair<int, int>> prv(size(), std::make_pair(-1, -1));
		while (true) {
			std::vector<int> visited;
			std::queue<int> que;
			prv[s].first = s;
			visited.emplace_back(s);
			que.emplace(s);
			while (!que.empty() && prv[t].first == -1) {
				const int u = que.front();
				que.pop();
				for (int i = 0; i < static_cast<int>(g[u].size()); ++i) {
					const int to = g[u][i].to;
					if (prv[to].first != -1 || g[u][i].c <= EPS) continue;
					prv[to] = {u, i};
					visited.emplace_back(to);
					if (to == t) break;
					que.emplace(to);
				}
			}
			if (prv[t].first == -1) break;
			cap_type flow = g[prv[t].first][prv[t].second].c;
			for (int u = prv[t].first; u != prv[u].first; u = prv[u].first) {
				flow = std::min(flow, g[prv[u].first][prv[u].second].c);
			}
			for (int u = t; u != prv[u].first; u = prv[u].first) {
				const auto [v, eidx] = prv[u];
				g[v][eidx].c -= flow;
				g[u][g[v][eidx].rev].c += flow;
			}
			for (int u : visited) prv[u] = {-1, -1};
			res += flow;
		}
		return res;
	}
};

最大流 (Edmonds-Karp) (GraphTheory/EdmondsKarp.hpp)

概要

コンストラクタ

EdmondsKarp(int n)

メンバ関数

int size()

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

T max_flow(int s, int t)

使用例

参考

Verified with

Code

最大流 (Edmonds-Karp)
(GraphTheory/EdmondsKarp.hpp)