フローの残余グラフ

components/flow_graph.hpp · GitHub で見る

共通ページ

flow_detail::Graph<Cap> は最大流・最小費用流で使う残余グラフです。正辺と逆辺を連続して保存します。

操作・メンバ	内容・返り値	計算量
Graph(n=0)	頂点数を指定して構築	\(O(1)\)
reserve(m)	元の辺 m 本分を確保	\(O(M)\)
add_edge(from,to,cap)	正辺と容量 0 の逆辺を追加し、元の辺番号を返す	償却 \(O(1)\)
build()	隣接する残余辺の添字を連続配列に構築。変更がなければ何もしない	初回: \(O(N+M)\)、構築済み: \(O(1)\)
reset_flow()	逆辺の容量を正辺へ戻し、流量を 0 にする	\(O(M)\)
n / built	頂点数／隣接配列が有効か	\(O(1)\)
arcs / Arc	to・cap を持つ残余辺の配列／その型。逆辺は添字の下位 bit を反転して得る	\(O(1)\)
start / order	頂点ごとの隣接区間／その区間に並ぶ残余辺の添字	\(O(1)\)

頂点は 0 始まり、容量は非負、元の辺数は INT_MAX/2 以下にします。容量型の条件は公開フローライブラリと同じです。

\(N\) 頂点・\(M\) 辺として、構築は \(O(1)\)、追加は償却 \(O(1)\)、初回・辺追加後の build は \(O(N+M)\)、その他の build は \(O(1)\)、reset_flow・領域を増やす reserve は \(O(M)\)、空間は \(O(N+M)\) です。

検証コード

• test/max_flow.test.cpp
• test/max_flow.test.cpp
• test/max_flow_yuki.test.cpp
• test/max_flow_yuki.test.cpp
• test/min_cost_b_flow.test.cpp
• test/min_cost_b_flow.test.cpp
• test/min_cost_flow.test.cpp
• test/min_cost_flow.test.cpp

コード

#ifndef FLOW_GRAPH_HPP
#define FLOW_GRAPH_HPP

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>

namespace flow_detail {
template<class Cap> struct Graph {
	struct Arc { int to; Cap cap; };
	int n;
	std::vector<Arc> arcs;
	std::vector<int> start, order;
	bool built = false;
	explicit Graph(int n = 0) : n(n) { assert(n >= 0); }
	void reserve(std::size_t m) { assert(m <= std::size_t(std::numeric_limits<int>::max() / 2)); arcs.reserve(2 * m); }
	int add_edge(int from, int to, Cap cap) {
		assert(0 <= from && from < n && 0 <= to && to < n && cap >= 0);
		assert(arcs.size() <= std::size_t(std::numeric_limits<int>::max() - 2));
		int id = int(arcs.size());
		arcs.push_back({to, cap});
		arcs.push_back({from, Cap(0)});
		built = false;
		return id / 2;
	}
	void build() {
		if (built) return;
		start.assign(std::size_t(n) + 1, 0);
		for (std::size_t i = 0; i < arcs.size(); ++i) ++start[arcs[i ^ 1].to + 1];
		for (int v = 0; v < n; ++v) start[v + 1] += start[v];
		order.resize(arcs.size());
		auto next = start;
		for (int i = 0; i < int(arcs.size()); ++i) order[next[arcs[i ^ 1].to]++] = i;
		built = true;
	}
	void reset_flow() {
		for (std::size_t i = 0; i < arcs.size(); i += 2) arcs[i].cap += arcs[i + 1].cap, arcs[i + 1].cap = 0;
	}
};
}

#endif

Back to top page