MaxFlow 構造体

最大流 [詳解]

#include "max_flow.hpp"

クラス
struct	Edge
	辺構造体 [詳解]

公開メンバ関数
	MaxFlow (int n)
	MaxFlow ()=default
void	add_edge (int from, int to, ll cap)
	容量 cap の辺を追加する
ll	flow (int s, int t)
	s から t への最大流を求める
vector< int >	mincut (int v=0)
	直前に流したフローから最小カットを復元する
vector< Edge >	get_edges ()
	直前に流したフローの辺の情報を返す

詳解

最大流

max_flow.hpp の 5 行目に定義があります。

構築子と解体子

MaxFlow() [1/2]

MaxFlow::MaxFlow ( int n )

inline

max_flow.hpp の 17 行目に定義があります。

MaxFlow() [2/2]

MaxFlow::MaxFlow ( )

default

関数詳解

add_edge()

void MaxFlow::add_edge ( int from, int to, ll cap )

inline

容量 cap の辺を追加する

max_flow.hpp の 21 行目に定義があります。

flow()

ll MaxFlow::flow ( int s, int t )

inline

s から t への最大流を求める

覚え書き

O(V^2 E)

max_flow.hpp の 61 行目に定義があります。

参照先 INFL.

mincut()

vector< int > MaxFlow::mincut ( int v = 0 )

inline

直前に流したフローから最小カットを復元する

始点 v から到達可能か否か

max_flow.hpp の 74 行目に定義があります。

get_edges()

vector< Edge > MaxFlow::get_edges ( )

inline

直前に流したフローの辺の情報を返す

max_flow.hpp の 90 行目に定義があります。

---

この構造体詳解は次のファイルから抽出されました:

• graph/flow/max_flow.hpp