アルゴリズム辞典

Primal-Dual

流量 3 の最小費用流

説明

最小費用流を最短路反復で解くアルゴリズム。始点から終点までの重みの最短路を求め、そこに流せる限り流す。これを流したい分だけ流しきるまで繰り返す。最短路の計算は、ポテンシャル h を用いて負辺がないように変換して Dijkstra法で求める。

情報

項目	データ
計算量	$O(FElogV)$

項目

データ

計算量

$O(FElogV)$

関数

add_edge(from, to, cap, cost)
機能	$from$ から $to$ へ, 容量 $cap$, 費用 $cost$ の辺を張る。

add_edge(from, to, cap, cost)

機能

$from$ から $to$ へ, 容量 $cap$, 費用 $cost$ の辺を張る。

min_cost_flow(s, t, f)
機能	$s$ から $t$ へ, 流量 $f$ の最小費用流を返す。$f$を流せないときとき、-1。

min_cost_flow(s, t, f)

機能

$s$ から $t$ へ, 流量 $f$ の最小費用流を返す。$f$を流せないときとき、-1。