最大流・最小カット
概要
選択・排反・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を避ける。
問題一覧
- ABC318 G「Typical Path Problem」 公式問題
- ABC239 G「Builder Takahashi」 公式問題
- ABC241 G「Round Robin」 公式問題
- ABC259 G「Grid Card Game」 公式問題
- ABC326 G「Unlock Achievement」 公式問題
- ABC225 G「X」 公式問題
- ABC263 G「Erasing Prime Pairs」 公式問題組合せ: 一次元凸・単峰最適化
技能・出典
主題: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 最大流・最小カット / 補助タグ: 一次元凸・単峰最適化
- ABC332 G「Not Too Many Balls」 公式問題
技能・出典
主題: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 最大流・最小カット / 補助タグ: event・値順のオフライン走査、資源軸knapsack DP
- ABC437 G「Colorful Christmas Tree」 公式問題
技能・出典
主題: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。 二部彩色を前提に、頂点・色組の使用回数A_{v,k}を容量へ写す最大流のモデルを学ぶ。流量N−1から各木辺の削除時の色対を固定する。一対一matchingではない。次に、実行可能な辺がないと仮定して葉から根へ条件を伝播させると矛盾することを示す。一辺削除した後も残りの回数制約が保たれるため、この存在証明を帰納的に繰り返して操作列を復元できる。静的な割当の可否と時系列の実行可能性を別々に証明する。主タグ: 最大流・最小カット / 補助タグ: 二部グラフの彩色と成分構造、構成解・witness復元
- ABC347 G「Grid Coloring 2」 公式問題
- ABC397 G「Maximize Distance」 公式問題組合せ: 単調境界を証明して探索する
技能・出典
主題: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。 - ABC227 H「Eat Them All」 公式問題
技能・出典
主題: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: Euler trail・circuit(全辺を一度ずつ使うEuler trail・circuitについて、無向graphの奇数次数条件または有向graphの入出次数条件と辺を持つ部分の連結性から存在を判定し、具体的な辺列が必要ならHierholzer法で構成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: Euler trail・circuit、最大流・最小カット / 補助タグ: 有界全列挙・有限case分解
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC285 G「Tatami」 公式問題主題: 下限制約付きflowの実現可能性
技能・出典
主題: 下限制約付きflowの実現可能性(各辺のlower boundを先に流して頂点需要へ変換し、super source/sinkを加えたcirculationの飽和可能性を判定する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 下限制約付きflowの実現可能性 / 補助タグ: 最大流・最小カット
- ABC354 G「Select Strings」 公式問題
技能・出典
主題: 半順序・Dilworth・最大反鎖(対象を半順序へ写し、Dilworth型のchain/antichain双対をLDS・matching・min-cutの適切な形で解ける。)。既習技能: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 半順序・Dilworth・最大反鎖 / 補助タグ: 最大流・最小カット
前提・学習成果・出典
習得対象の目安: 青色(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では扱わないもの
- 最大流・最小カットの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。