最小費用流
最小費用流に帰着
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