最大流

graph/max_flow.hpp · GitHub で見る

共通ページ

#include "lib/graph/max_flow.hpp"

MaxFlow<> graph(3);
graph.add_edge(0, 1, 5);
graph.add_edge(1, 2, 3);
auto flow = graph.flow(0, 2);
auto cut = graph.min_cut(0);

操作・型	内容・返り値	計算量
MaxFlow<Cap>(n=0)	n 頂点で構築。Cap の既定は std::int64_t	\(O(N)\)
size() / edge_count()	頂点数／追加した辺数	\(O(1)\)
reserve(m)	元の辺 m 本分の領域を確保	\(O(M)\)
add_edge(from,to,cap)	有向辺を追加し、0 始まりの辺番号を返す	償却 \(O(1)\)
flow(s,t)	最大流まで流し、今回追加した流量を返す。Highest Label Push-Relabel を使う	\(O(N^2M)\)、初回は別途 \(O(N+M)\)
flow(s,t,limit)	今回の流量を limit 以下に制限し、追加した流量を返す。反復版 Dinic を使う	\(O(N^2M)\)、初回は別途 \(O(N+M)\)
min_cut(s)	残余グラフで s から到達できるかを vector<bool> で返す	\(O(N+M)\)
get_edge(i)	追加時の順番で辺の情報を返す	\(O(1)\)
edges()	全ての辺の情報を vector<Edge> で返す	\(O(M)\)
change_edge(i,cap,flow)	辺の容量と流量を変更。0 <= flow <= cap が必要	\(O(1)\)
reset_flow()	全ての流量を 0 に戻す。頂点と辺は残す	\(O(M)\)
Edge	from・to・cap・flow を持つ	—（型）

頂点は 0 始まりです。自己辺・多重辺・容量 0 に対応します。Cap は 64 bit 以下の標準整数型で、bool を除きます。容量・流量上限は非負、返す流量と各辺の容量は Cap に収めます。Push-Relabel の途中の余剰流量は 128 bit で持つため、始点から出る容量の総和が Cap を超える場合も扱えます。

s != t が必要です。頂点数は INT_MAX/2-1 以下、元の辺数は INT_MAX/2 以下にします。再帰を使わないため、長いパスも扱えます。

残余グラフを保持するため、同じ始点・終点で繰り返し呼ぶと続きを流します。辺を追加してから続けることもできます。change_edge で現在のフローを変更する場合は、始点・終点以外の流量保存則を保ってください。最小カットが必要な場合は、flow(s,t) で最大流まで流した後に min_cut(s) を呼びます。

\(N\) 頂点・\(M\) 辺として、構築は \(O(N)\) 以下、辺追加は償却 \(O(1)\)、最大流はどちらも一般の上界が \(O(N^2M)\)、min_cut は \(O(N+M)\) です。辺追加後の最初の流量計算・min_cut には隣接配列の構築 \(O(N+M)\) が加わります。get_edge・値取得・change_edge は \(O(1)\)、edges・reset_flow は \(O(M)\)、領域を増やす reserve は \(O(M)\)、空間は \(O(N+M)\) です。

依存ライブラリ

• フローの残余グラフ
• Push-Relabel の内部演算

検証コード

• test/max_flow.test.cpp
• test/max_flow_yuki.test.cpp

コード

#ifndef MAX_FLOW_HPP
#define MAX_FLOW_HPP

#include "../components/flow_graph.hpp"
#include "../components/push_relabel.hpp"
#include <cstdint>
#include <type_traits>

template<class Cap = std::int64_t> class MaxFlow {
	static_assert(std::is_integral_v<Cap> && !std::is_same_v<Cap, bool> && sizeof(Cap) <= 8);
	flow_detail::Graph<Cap> graph_;
	void vertex([[maybe_unused]] int v) const { assert(0 <= v && v < graph_.n); }
	int index(int i) const { assert(0 <= i && std::size_t(i) < graph_.arcs.size() / 2); return 2 * i; }

  public:
	struct Edge { int from, to; Cap cap, flow; };
	explicit MaxFlow(int n = 0) : graph_(n) {}
	int size() const { return graph_.n; }
	int edge_count() const { return int(graph_.arcs.size() / 2); }
	void reserve(std::size_t m) { graph_.reserve(m); }
	int add_edge(int from, int to, Cap cap) { return graph_.add_edge(from, to, cap); }
	Edge get_edge(int i) const {
		int j = index(i);
		const auto& a = graph_.arcs[j];
		const auto& b = graph_.arcs[j ^ 1];
		return {b.to, a.to, Cap(a.cap + b.cap), b.cap};
	}
	std::vector<Edge> edges() const {
		std::vector<Edge> result;
		result.reserve(edge_count());
		for (int i = 0; i < edge_count(); ++i) result.push_back(get_edge(i));
		return result;
	}
	void change_edge(int i, Cap cap, Cap flow) {
		assert(0 <= flow && flow <= cap);
		int j = index(i);
		graph_.arcs[j].cap = cap - flow, graph_.arcs[j ^ 1].cap = flow;
	}
	void reset_flow() { graph_.reset_flow(); }
	Cap flow(int s, int t) {
		vertex(s), vertex(t);
		assert(s != t);
		return flow_detail::push_relabel(graph_, s, t);
	}
	Cap flow(int s, int t, Cap limit) {
		vertex(s), vertex(t);
		assert(s != t && limit >= 0);
		graph_.build();
		auto& g = graph_;
		std::vector<int> level(g.n), iter(g.n), queue(g.n);
		struct Frame { int v; Cap limit, sent; };
		std::vector<Frame> stack;
		stack.reserve(g.n);
		Cap total = 0;
		while (total < limit) {
			std::fill(level.begin(), level.end(), -1);
			level[s] = 0;
			int head = 0, tail = 0;
			queue[tail++] = s;
			while (head < tail && level[t] < 0) {
				int v = queue[head++];
				for (int i = g.start[v]; i < g.start[v + 1]; ++i) {
					const auto& e = g.arcs[g.order[i]];
					if (!e.cap || level[e.to] >= 0) continue;
					level[e.to] = level[v] + 1;
					queue[tail++] = e.to;
				}
			}
			if (level[t] < 0) break;
			std::copy_n(g.start.begin(), g.n, iter.begin());
			stack.push_back({t, Cap(limit - total), Cap(0)});
			while (!stack.empty()) {
				auto& frame = stack.back();
				int v = frame.v;
				if (v == s || frame.sent == frame.limit || iter[v] == g.start[v + 1]) {
					Cap sent = v == s ? frame.limit : frame.sent;
					if (v != s && sent < frame.limit) level[v] = g.n;
					stack.pop_back();
					if (stack.empty()) { total += sent; break; }
					auto& parent = stack.back();
					int id = g.order[iter[parent.v]];
					g.arcs[id].cap += sent, g.arcs[id ^ 1].cap -= sent;
					parent.sent += sent;
					if (parent.sent < parent.limit) ++iter[parent.v];
				} else {
					int id = g.order[iter[v]];
					const auto& e = g.arcs[id];
					if (level[e.to] < 0 || level[e.to] >= level[v] || !g.arcs[id ^ 1].cap) ++iter[v];
					else stack.push_back({e.to, std::min<Cap>(frame.limit - frame.sent, g.arcs[id ^ 1].cap), Cap(0)});
				}
			}
		}
		return total;
	}
	std::vector<bool> min_cut(int s) {
		vertex(s);
		graph_.build();
		std::vector<bool> visited(graph_.n);
		std::vector<int> queue{ s };
		visited[s] = true;
		for (std::size_t head = 0; head < queue.size(); ++head) {
			int v = queue[head];
			for (int i = graph_.start[v]; i < graph_.start[v + 1]; ++i) {
				const auto& e = graph_.arcs[graph_.order[i]];
				if (e.cap && !visited[e.to]) visited[e.to] = true, queue.push_back(e.to);
			}
		}
		return visited;
	}
};

#endif

Back to top page