mf_graph

template <class Cap>
struct mf_graph;

概要

最大流

名前	説明	計算量
`(constructor)`	(1) 0頂点のグラフを構築する (2) n頂点0辺のグラフを構築する	(1) $O(1)$ (2) $O(n)$

名前	説明	計算量
`size`	頂点数を返す	$O(1)$
`add_edge`	容量capの有向辺を追加して辺IDを返す	償却 $O(1)$
`get_edge`	指定した辺の現在状態を返す	$O(1)$
`edges`	全辺の現在状態を追加順で返す	辺数を $E$ として $O(E)$
`change_edge`	辺の容量と現在流量を変更する	$O(1)$
`flow`	(1) sからtへ流せるだけ流して追加流量を返す (2) sからtへflow_limitまで流して追加流量を返す	(1) 頂点数を $V$、辺数を $E$ として $O(V^2E)$ (2) $O(V^2E)$
`min_cut`	残余グラフでsから到達可能な頂点集合を返す	$O(V+E)$

名前	説明	計算量
`edge`	追加した辺の現在状態	各フィールドへのアクセスは $O(1)$

// (1)
mf_graph();

// (2)
explicit mf_graph(int n);

(1) 0頂点のグラフを構築する

(2) n頂点0辺のグラフを構築する

// (1)
Cap flow(int s, int t);

// (2)
Cap flow(int s, int t, Cap flow_limit);

(1) sからtへ流せるだけ流して追加流量を返す

(2) sからtへflow_limitまで流して追加流量を返す

struct edge;

追加した辺の現在状態

メンバ	説明
`to`	辺の始点と終点
`flow`	辺の容量と現在の流量