Minimum Cost Flow with Capacity Scaling
(bflow/capacityscaling.cpp)
INF
の決め方
上限
m * INF
がオーバーフローすると死ぬことがある
下限
max - INF < min
を満たしていないと区別できない
結論
max - min < INF < 2^w / m
w
はビット幅
解説記事
Are there any learning materials of polynomial minimum cost flow algorithms?
ぼくの考えたさいきょうのフローライブラリ
最小費用流の双対について
b-flow と双対
Verified with
Code
Back to top page