最小費用流

NISHIO Hirokazu [Translate]

最小費用流
最小費用流に帰着

Primal-Dual / 最短路反復法
O(V^2UC) Spaghetti Source - 最小費用流 (Primal-Dual)
O(FElogV) 最小費用流 | libalgo
O(FElogV) 最小費用流(Primal-Dual) | Luzhiled’s memo



https://www.hamayanhamayan.com/entry/2017/05/09/120428
Spaghetti Source - 最小費用流 (Primal-Dual)
ポテンシャルを使うことで負の辺をなくし、ダイクストラ法に帰着
Primal Dual 

最小費用流 | libalgo
なぜ主双対か
https://kopricky.github.io/code/NetworkFlow/min_cost_flow_memo.html

flow_bunkakai_memo.md · GitHub

http://hos.ac/slides/20150319_flow.pdf


発展的話題
http://sigma425.hatenablog.com/entry/2014/10/12/122018

http://tokoharuland.hateblo.jp/entry/2019/12/25/000000



蟻本p202

他の人の実装
https://ei1333.github.io/luzhiled/snippets/graph/primal-dual.html

→最小カットに帰着×最大流×project_selection_problem×aclpc_d×最大二部マッチング×帰着する力×最小費用流に帰着→

最大流に帰着

→ダイクストラ法×定義域より値域が狭い関数×値域と定義域の交換×ゆるい逆写像×実数に対する大小判定×二分探索チェックリスト→

ABC191

→chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→

貪欲法

→僕のatcoderの学び方(〜水色)×僕のatcoderの学び方(〜past上級)×abc187×PAST過去問練習202012×変形テクニックに名前をつける×頂点数18の制約×辺が10^5の制約×行列の半分×二項定理×足し算の順序の変更×辺が10^5ならダイクストラ使える×典型力×問題変換×問題分割×認知の解像度×概念のハンドル×atcoder失敗リスト×atcoderentrypoint×アルゴリズム実技検定×第五回アルゴリズム実技検定×最小費用流に帰着×帰着訓練→

僕のatcoderの学び方(〜青)

→past5×past202012×アルゴリズム実技検定×PAST過去問練習202012×past5e×past5f×past5g×past5h×PAST5I×past5j×past5k×past5l×past5m×past5n×past5o×番兵×地図読み込み時に番兵をつける×ゴールをスタートにする×ゴールを一つにする×ダイクストラ法×bit_dp×期待値dp×二次元の片方を時間軸にする×past2n→