最大流・最小カット
選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。
この典型を扱う単元: 最大流・最小カット
検索別名: max flow、min cut、最大流、最小カット
未知問からこの典型を見つける手掛かり
- 扱う対象
- capacity network
- cut
- sink
- source
- 使う手掛かり
- closure
- 二値選択
- 容量
- 排反
- 保つ不変量
- cut capacity
- flow conservation
- residual graph
- 求めるもの
- cut復元
- 最大選択
- 最小除去
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- 二部matching・Hall・Kőnig: 二部matchingをunit-capacity flowへ帰着し、Kőnig型双対をmin-cutから説明するときに併用する。
学習成果と学習単位
選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
最大流・最小カットで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC241 G「Round Robin」 公式問題主題: 最大流・最小カット / 主タグ
- ABC225 G「X」 公式問題主題: 最大流・最小カット / 主タグ
- ABC239 G「Builder Takahashi」 公式問題主題: 最大流・最小カット / 主タグ
- ABC227 H「Eat Them All」 公式問題主題: 最大流・最小カット / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC225 G「X」 公式問題主題: 最大流・最小カット / 主タグ
- ABC227 H「Eat Them All」 公式問題主題: 最大流・最小カット / 主タグ
- ABC239 G「Builder Takahashi」 公式問題主題: 最大流・最小カット / 主タグ
- ABC241 G「Round Robin」 公式問題主題: 最大流・最小カット / 主タグ
- ABC259 G「Grid Card Game」 公式問題主題: 最大流・最小カット / 主タグ
- ABC263 G「Erasing Prime Pairs」 公式問題主題: 最大流・最小カット / 主タグ
- ABC285 G「Tatami」 公式問題主題: 下限制約付きflowの実現可能性 / 補助タグ
- ABC318 G「Typical Path Problem」 公式問題主題: 最大流・最小カット / 主タグ
- ABC326 G「Unlock Achievement」 公式問題主題: 最大流・最小カット / 主タグ
- ABC332 G「Not Too Many Balls」 公式問題主題: 最大流・最小カット / 主タグ
- ABC347 G「Grid Coloring 2」 公式問題主題: 最大流・最小カット / 主タグ
- ABC354 G「Select Strings」 公式問題主題: 半順序・Dilworth・最大反鎖 / 補助タグ
- ABC397 G「Maximize Distance」 公式問題主題: 最大流・最小カット / 主タグ
- ABC437 G「Colorful Christmas Tree」 公式問題主題: 最大流・最小カット / 主タグ