最小費用流
(mincostflow/primaldual.cpp)
解説記事
最小費用流の双対について
計算量
流量を $F$ として、$O(F E \log V)$
ポテンシャルの初期化
コストが負の辺が存在する場合、 build
の際に init
を渡すことでポテンシャルの初期化の仕方を指定できる。
一般の場合には bellman-ford を用いて $O(VE)$ で初期化する。
DAG の場合には DP を用いて $O(E)$ で初期化することもできる。例
コストが負の辺の最大流量の和が小さい場合は、最小費用流の負辺除去 を使用する。
Required by
Verified with
Code
Back to top page