読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

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

最大流

  • Max flow
  • 有向グラフで各辺ごとに流せる水の量が決まっていて、始点から終点まで最大どれだけの量流せるかを判定する
  • 参考1 参考2 参考3
  • Dinic法はO(V^2E)、フォード・ファルカーソンではO(E*maxflow)
  • 辺の貼り方の最強スライド
  • 最大流を応用すると「二部マッチング」が解ける

hamayanhamayan.hatenablog.jp

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

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

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

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