はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける最小費用流問題まとめ

最小費用流

  • Min Cost Flow
  • 最大流の辺にコストがついたもので、ソースからシンクへある量のフローを流す時の各辺のフローとコストの積の総和を最小化する
  • コストを損失と考えて最大化問題を解く考え方がよく使われる(こっちでそれを練習してからの方がいいかも)
  • アルゴリズムは2つあるっぽく、制約が厳しいときは使い分けないといけないかも(不確定な情報)

1. O(V^2UC)のやつ -> 辺の数が多いときはこっち 実装
2. O(fElogV)のやつ -> 費用が大きいときはこっち 実装

  • ネットワーク単体法が最速アルゴリズムらしいが、今まで上の2つで通らなかった問題はみたことがない
  • こういう発展的話題もある
  • 最小費用循環流というもある(ソースとシンクが無い最小費用流らしい、最小費用流に帰着できるらしい)
  • コストが「個数^2」とか「2^個数」とかに成るやつは差分のコストを追加していくと表現できる 例題