MinCostFlow 構造体

最小費用流 [詳解]

#include "min_cost_flow.hpp"

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

公開メンバ関数
	MinCostFlow (int n)
void	add_edge (int from, int to, ll cap, ll cost)
	s -> t に容量 cap, コスト cost の辺を追加する
vector< Edge >	get_edges ()
	全ての辺を返す
ll	flow (int s, int t, ll f)
	s から t へ流量 f の最小費用流のコストを求める

詳解

最小費用流

覚え書き

コスト負の辺を許容する。負の閉路はダメ。

min_cost_flow.hpp の 6 行目に定義があります。

構築子と解体子

MinCostFlow()

MinCostFlow::MinCostFlow ( int n )

inline

min_cost_flow.hpp の 18 行目に定義があります。

関数詳解

add_edge()

void MinCostFlow::add_edge ( int from, int to, ll cap, ll cost )

inline

s -> t に容量 cap, コスト cost の辺を追加する

覚え書き

cost は負でも良い

min_cost_flow.hpp の 22 行目に定義があります。

get_edges()

vector< Edge > MinCostFlow::get_edges ( )

inline

全ての辺を返す

覚え書き

O(V+E)

直前に流した flow による残余であることに注意

min_cost_flow.hpp の 30 行目に定義があります。

flow()

ll MinCostFlow::flow ( int s, int t, ll f )

inline

s から t へ流量 f の最小費用流のコストを求める

流せない場合は INFL を返す

覚え書き

O(FE log V)

min_cost_flow.hpp の 39 行目に定義があります。

参照先 INFL.

---

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

• graph/flow/min_cost_flow.hpp