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

hamayanhamayan's blog

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

最大流

  • Max flow
  • 有向グラフで各辺ごとに流せる水の量が決まっていて、始点から終点まで最大どれだけの量流せるかを判定する
  • 参考1 参考2 参考3
  • Dinic法はO(V^2E)、フォード・ファルカーソンではO(E*maxflow)
  • 辺の貼り方の最強スライド『燃やす埋める問題』
  • 最大流を応用すると「二部マッチング」が解ける
  • 最大フロー最小カット定理 参考1 参考2
  • 木のある部分木全体にフローを張りたい時は、子供に容量INFの辺を事前に張っておくことで、部分木の根に辺を張るだけで部分木全体に辺を張る効果が得られるみたい 問題
  • 全体の流量を変えずに別の最大流を求めるテクがある(蟻本p.193) 問題
  • LP双対というのがある(最小値を最大値に変えて解くためのテク?全然分かってない)

【発展的話題】最小流量制限付き最大流

最小流量制限付き最大流というのもある

  • 上手く変形することで最小流量をなくした最大流問題に変換できる(この記事や蟻本p.193の手法)
  • 最小費用流でも同じようにやってできるらしい

問題
yukicoder No.459 C-VS for yukicoder 解説
SRM 694 Div1 Hard SRMDiv0Easy 解説2 解説2
ICPC Live Archive 4268 Bonus Adjustment 解説