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
-
なぜ主双対か
-
発展的話題
http://tokoharuland.hateblo.jp/entry/2019/12/25/000000
蟻本p202
他の人の実装