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

hamayanhamayan's blog

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

最大流

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

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

  • 上手く変形することで最小流量をなくした最大流問題に変換できる(この記事や蟻本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 ←最小流用制限付き最小費用流かもしれない(そんなのない?これにもっとやばそうなのある)