二部matching・Hall・Kőnig
左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。
この典型を扱う単元: 二部matching・Hall・Kőnig
検索別名: Hallの定理、Kőnigの定理、bipartite matching、二部マッチング
未知問からこの典型を見つける手掛かり
- 扱う対象
- matching
- 対応辺
- 左右頂点集合
- 使う手掛かり
- path cover
- 一対一割当
- 近傍集合
- 保つ不変量
- Hall condition
- augmenting path
- 交互路
- 求めるもの
- 完全割当
- 最大matching
- 最小被覆
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- 最大流・最小カット: 二部matchingをunit-capacity flowへ帰着し、Kőnig型双対をmin-cutから説明するときに併用する。
- 一般グラフの最小重み完全matching: 二部性を使えるaugmenting path・Hall型議論と、odd blossomを扱う一般graph完全matchingを対比する。
学習成果と学習単位
二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。
二部matching・Hall・Kőnigで学ぶ左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
二部matching・Hall・Kőnigで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC215 H「Cabbage Master」 公式問題主題: 二部matching・Hall・Kőnig / 主タグ
- ABC237 Ex「Hakata」 公式問題主題: 半順序・Dilworth・最大反鎖 / 補助タグ
- ABC274 G「Security Camera 3」 公式問題主題: 二部matching・Hall・Kőnig / 主タグ
- ABC313 Ex「Group Photo」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC317 G「Rearranging」 公式問題主題: 二部matching・Hall・Kőnig / 主タグ
- ABC318 F「Octopus」 公式問題主題: 整数境界と同値区間を正確に分ける / 補助タグ
- ABC320 G「Slot Strategy 2 (Hard)」 公式問題主題: 二部matching・Hall・Kőnig / 主タグ
技能・出典
主タグ: 二部matching・Hall・Kőnig / 補助タグ: 座標・値の順序保存圧縮、貪欲法と交換論、剰余周期・指数法則、単調境界探索
- ABC363 G「Dynamic Scheduling」 公式問題主題: rollback・DFS入退場の状態復元 / 補助タグ
技能・出典
主タグ: rollback・DFS入退場の状態復元 / 補助タグ: 二部matching・Hall・Kőnig、遅延評価する区間作用、Segment Treeのcanonical区間分解
- ABC374 G「Only One Product Name」 公式問題主題: 二部matching・Hall・Kőnig / 主タグ
- ABC401 G「Push Simultaneously」 公式問題主題: 二部matching・Hall・Kőnig / 主タグ
- ABC424 G「Set list」 公式問題主題: 資源・容量DP / 補助タグ
- ABC445 G「Knight Placement」 公式問題主題: 二部matching・Hall・Kőnig / 主タグ
- ABC461 G「Graph Problem 2026」 公式問題主題: 二部matching・Hall・Kőnig / 主タグ