フロー

Links

• https://www.youtube.com/watch?v=vVJNlhQtfgo
  • https://img.atcoder.jp/TOYOTA_AHC_AlgorithmExplanatoryMeeting2/morita.pdf
• https://ocw.mit.edu/courses/15-082j-network-optimization-fall-2010/pages/lecture-notes/

最小費用流

• https://en.wikipedia.org/wiki/Minimum-cost_flow_problem
• いくつかアプローチがあって、グラフの特性によって速度に差がでうる

アプローチ

• Primal-Dual
• Cost Scaling
• Network Simplex
  • https://codeforces.com/blog/entry/94190
  • https://people.orie.cornell.edu/dpw/orie6300/Lectures/lec14.pdf

Library

• https://en.wikipedia.org/wiki/LEMON_(C%2B%2B_library)
  • https://lemon.cs.elte.hu/trac/lemon/wiki/MinCostFlowData
• https://judge.yosupo.jp/problem/min_cost_b_flow

問題

• AHC034