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

最大流

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

• グラフの一部が変更された時に差分だけ計算することで高速に計算する手法がある 問題 解説1 解説2 解説3 解説4

問題

• AOJ 最大流
• QUPC2014 H. お風呂は気持ちいい
• ARC074 F. Lotus Leaves
• yukicoder No.177 制作進行の宮森あおいです！　解説
• yukicoder No.654 Air E869120 解説
• CC Bipartite Graph from Trees
• Codeforces Round #304 (Div. 2) E. Soldier and Traveling
• Waiwai Otaku Panic
• yukicoder No.119 旅行のツアーの問題
• AtCoder Make a Potion 解説1 解説2
• Infinite Network
• KUPC2016 E. 柵
• 東京工業大学プログラミングコンテスト2015 L.グラフ色ぬり
• ARC031 D. 買い物上手
• Educational Codeforces Round 8: F. Bear and Fair Set
• RUPC2018 Day3 最短距離を伸ばすえびちゃん (Ebi-chan Lengthens Shortest Paths) 解説（最小カット）

• 燃やす埋める問題(最小カット)
  • ARC085 MUL
  • AOJ 板 解説
  • AOJ 板
  • AOJ イルミネーション
  • AOJ Ghost

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

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

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

問題
yukicoder No.459 C-VS for yukicoder 解説
SRM 694 Div1 Hard SRMDiv0Easy 解説2 解説2
ICPC Live Archive 4268 Bonus Adjustment 解説
AGC031 Snuke the Phantom Thief ←最小流用制限付き最小費用流かもしれない（そんなのない？これにもっとやばそうなのある）