Push-Relabel の内部演算

components/push_relabel.hpp · GitHub で見る

共通ページ

最大流 の内部部品です。Highest Label、Gap、Global Relabel を使います。余剰流量は 128 bit で保持します。

操作	内容・返り値	計算量
flow_detail::push_relabel(graph,s,t)	Graph<Cap> の残余グラフから最大流まで追加し、その流量を返す	\(O(N^2M)\)

公開ライブラリと同じ前提条件が必要です。頂点は異なる有効な番号を指定し、返す流量は容量型に収めます。

\(N\) 頂点・\(M\) 辺として、一般の上界は \(O(N^2M)\) 時間、\(O(N+M)\) 空間です。

依存ライブラリ

• フローの残余グラフ

検証コード

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

コード

#ifndef PUSH_RELABEL_HPP
#define PUSH_RELABEL_HPP

#include "flow_graph.hpp"
#include <cstdint>

namespace flow_detail {
template<class Cap> Cap push_relabel(Graph<Cap>& graph, int s, int t) {
	graph.build();
	int n = graph.n;
	assert(n <= std::numeric_limits<int>::max() / 2 - 1);
	int dead = 2 * n;
	std::vector<__uint128_t> excess(n);
	std::vector<int> height(n), current(n), count(std::size_t(dead) + 1), head(std::size_t(dead) + 1, -1), next(n), queue(n);
	std::vector<unsigned char> active(n);
	int highest = -1;
	std::size_t work = 0, threshold = std::max<std::size_t>(1, 4 * graph.arcs.size() + n);
	auto activate = [&](int v) {
		if (v == s || v == t || active[v] || !excess[v] || height[v] == dead) return;
		active[v] = 1;
		next[v] = head[height[v]], head[height[v]] = v;
		highest = std::max(highest, height[v]);
	};
	auto buckets = [&] {
		std::fill(head.begin(), head.end(), -1);
		std::fill(active.begin(), active.end(), 0);
		highest = -1;
		for (int v = 0; v < n; ++v) activate(v);
	};
	auto global = [&] {
		std::fill(height.begin(), height.end(), n + 1);
		std::fill(count.begin(), count.end(), 0);
		std::copy_n(graph.start.begin(), n, current.begin());
		height[s] = n, height[t] = 0;
		int first = 0, last = 0;
		queue[last++] = t;
		while (first < last) {
			int v = queue[first++];
			for (int j = graph.start[v]; j < graph.start[v + 1]; ++j) {
				int i = graph.order[j], u = graph.arcs[i].to;
				if (u != s && height[u] == n + 1 && graph.arcs[i ^ 1].cap) height[u] = height[v] + 1, queue[last++] = u;
			}
		}
		for (int h : height) ++count[h];
		buckets();
		work = 0;
	};
	for (int j = graph.start[s]; j < graph.start[s + 1]; ++j) {
		int i = graph.order[j];
		auto& e = graph.arcs[i];
		if (e.to == s || !e.cap) continue;
		excess[e.to] += e.cap, graph.arcs[i ^ 1].cap += e.cap, e.cap = 0;
	}
	global();
	while (highest >= 0) {
		if (head[highest] < 0) { --highest; continue; }
		int v = head[highest];
		head[highest] = next[v];
		if (!active[v] || height[v] != highest) continue;
		active[v] = 0;
		while (excess[v] && height[v] < dead) {
			if (current[v] == graph.start[v + 1]) {
				int old = height[v], value = dead;
				for (int j = graph.start[v]; j < graph.start[v + 1]; ++j) {
					const auto& e = graph.arcs[graph.order[j]];
					if (e.cap) value = std::min(value, height[e.to] + 1);
				}
				work += graph.start[v + 1] - graph.start[v];
				--count[old], ++count[value], height[v] = value, current[v] = graph.start[v];
				if (old < n && !count[old]) {
					for (int u = 0; u < n; ++u) if (old < height[u] && height[u] < n) {
						--count[height[u]], height[u] = n + 1, ++count[n + 1], current[u] = graph.start[u];
					}
					buckets();
					break;
				}
			} else {
				++work;
				int i = graph.order[current[v]];
				auto& e = graph.arcs[i];
				if (!e.cap || height[v] != height[e.to] + 1) { ++current[v]; continue; }
				Cap amount = Cap(std::min(excess[v], __uint128_t(e.cap)));
				e.cap -= amount, graph.arcs[i ^ 1].cap += amount;
				excess[v] -= amount, excess[e.to] += amount;
				activate(e.to);
			}
		}
		activate(v);
		if (work >= threshold) global();
	}
	assert(excess[t] <= __uint128_t(std::numeric_limits<Cap>::max()));
	return Cap(excess[t]);
}
}

#endif

Back to top page