最大流・最小カット

概要

選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。

まず各辺の容量、内部頂点の流量保存、sourceからsinkへの流量を定める。残余辺は割当の取り消しと付け替えを表す。増加路がなくなったとき、sourceから残余到達可能な集合が同じ値のcutを与える。整数容量なら整数の割当を得られる。

基本形はsource→item(容量1)→受け手→sink(受け手の上限)であり、全item分の流量が存在するかを判定する。演習はABC318 Gから始め、頂点をin/outへ分けて頂点素経路を表す。ABC239 Gでは頂点費用のcutを作り、source側に残る頂点から削除集合を復元する。

ABC241 Gでは候補選手の未確定試合を全勝へ変えても優勝可能性を失わないことを示す。他選手の最終勝数を候補より1少なくする条件を、残り試合を選手へ割り当てる容量付きflowにする。既決着の勝数を各上限から差し引き、負の残枠を除く。この変換の正当化を、二つの基本的なflow・cut模型の後で学ぶ。

ABC259 G・ABC326 G・ABC225 Gで二値選択や含意制約をcutの容量へ写す。その後のABC437 Gは、頂点・色組の使用回数を容量として静的な色対割当を求めるだけでなく、常に削除できる辺があることを示して操作順まで復元する複合的な構成問題である。ABC332 Gでは巨大なnetworkをcutの式へ圧縮し、ナップサックDPと区分線形関数の走査につなぐ。

ABC347 G・ABC397 Gでは別のcut・flow還元を続け、ABC227 Hではflowによる判定をEuler路構成へ接続する。どの問題でも、cut容量が元の損失と一致する式と、割当を元の操作へ戻す根拠を確かめる。

考え方

残余graphの増加路に流量を送り、逆辺で以前の選択を取り消せるようにする。増加路がなくなると、始点から残余到達できる集合のcut容量が流量と一致して最適性の証拠になる。

増加の更新と帰着の復元

辺容量U・現在流量fには順残余U−f、逆残余fを持つ。増加路の最小残余Δを求め、順に使った残余をΔ減らし対応逆辺をΔ増やす。sから残余で届く集合Aにtがないとき、A→外の元辺は飽和、外→Aの元辺は流量0。保存式をA全体で足すとflow値=cut容量となり、全flowの上界を達成して最適である。ライブラリの最大流を使う場合も、元辺IDと最後の残余到達集合を返り値へ対応させる。

頂点vを高々c_v回使う制約はv_in→v_out容量c_v、元辺u→vはu_out→v_inにする。頂点削除費用のcutならc_vを費用とし、元接続辺は全有限費用和より大きい容量にする。cutが横切るin→out辺から削除頂点を復元する。

選択利益a_vを持つclosureではa_v>0ならs→v容量a_v、a_v<0ならv→t容量−a_v、v選択がu選択を要求するならv→uに大容量を張る。source側を選ぶ集合とするとcut容量は Σ_{a_v>0}a_v−選択利益 となる。大容量辺をcutしない最適解は含意を満たし、残余到達集合から選択を返せる。

成立条件と計算量

一般のDinicはO(V²E)が標準上界で、特殊な容量やgraphでは別の上界がある。容量は非負、逆辺の初期容量は通常0。無限容量は実際の有限上界より大きい値を選び、overflowを避ける。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。残余グラフとcutの意味を理解し、選択・排反を容量networkへ還元する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: フロー・マッチング・カットへ帰着する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-max-flow-min-cut

最大流・最小カット

習得する技能

  • 選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 状態グラフのモデリングと探索。

このUnitを直接前提とする単元: 下限制約付きflowの実現可能性、最小費用流・circulation、平面graph双対・cut/path対応。

状態グラフのモデリングと探索で得た考え方と実装を再利用し、最大流・最小カットの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 最大流・最小カットの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠