ABC 461 G — Graph Problem 2026

考察

各頂点 i を A_i,B_i に複製し、元辺 (u,v) ごとに A_u–B_v と A_v–B_u を結ぶ。左右の copy を部とする二部 graph である。

採用する候補: 最大 matching の大きさ μ を求め、1013(2N−μ) を答える。

Kőnig の定理から最大独立集合の大きさは 2N−μ。独立集合の indicator f から W_i=1013(f(A_i)+f(B_i)) を作ると実現可能な下界を得る。逆向きには任意の実現可能 W を copy 上へ等分し、matching の各辺と未匹配頂点を別々に足すことで同じ上界を示せる。

棄却する候補: 各 W_i を 0..2026 で探索する。

2027^N 通りの割当は扱えない。二部化しても元の実現可能解との対応を示さなければ、matching の値を答えとして使えない。

Hopcroft–Karp で二部最大 matching を計算する。孤立頂点も 2N 頂点に含める。

典型の発動条件

変数の二層複製による二部化

発動条件: 各元辺に対称な二つの組合せ制約がある重み割当問題のとき。

各変数をA/B copyに分けcross制約をedgeとして表す。

二部graphの最大独立集合

発動条件: 0/1選択でedge両端同時選択を禁止し総数を最大化するとき。

Königの定理で最大matchingの補数として求める。

問題固有の要素

同じ元変数を二つの copy へ等分すると、元の辺制約が各 cross edge 上の上界になる。matching が互いに素な制約をまとめ、未匹配頂点は個別上界で補う。

別の問題へ持ち帰る視点: 構成で得た下界に対し、互いに重ならない制約の和から上界を作り、最適性を挟み撃ちする。

正当性

最大独立集合の indicator を f とする。元辺 (u,v) の二本の cross edge では f(A_u)+f(B_v)≤1、f(A_v)+f(B_u)≤1。足すと W_u+W_v≤2026 であり、各 W_i も 0≤W_i≤2026。よって総和 1013(2N−μ) は実現できる。

逆に任意の実現可能 W に対し x(A_i)=x(B_i)=W_i/2026 と置く。各 x は [0,1] 内で、cross edge の両端の和は 1 以下である。大きさ μ の matching の両端は重複しないので、それらの x の和は μ 以下。残る 2N−2μ 頂点の和は 2N−2μ 以下。孤立頂点もこの後者に含まれる。したがって 2ΣW_i/2026=Σx≤2N−μ、すなわち ΣW_i≤1013(2N−μ)。下界と一致するので最適である。

実装上の注意

  • 元無向辺ごとにcross edgeを二方向分とも追加し、同じ元頂点のA_v-B_v辺は不要である。答え係数1013とMIS頂点数を混同しない。

復習の核

  • 独立集合からの構成と、任意の W を matching の両端・未匹配頂点へ分ける上界を両方再現する。孤立頂点を落とさない。

計算量と制約

時間

元N頂点M辺。二層2N頂点2M辺、Hopcroft–Karp O(M√N+N)。

空間

二層adjacencyとmatching O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 5 \times 10^4; 0 \leq M \leq 5 \times 10^4; 1 \leq u_i \lt v_i \leq N; (u_1,v_1),(u_2,v_2),\dots,(u_M,v_M) are pairwise distinct.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Graph Problem 2026 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 二部matching・Hall・Kőnig

主題
  • 二部matching・Hall・Kőnig: 左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 二部matching・Hall・Kőnig

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 二部matching・Hall・Kőnig

      • 左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      先に読む単元:

      • 二部彩色と成分構造を扱う — 無向グラフを探索できることを前提に二部性と部の交換対称性を扱い、連結二部グラフの彩色重複も補正する。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題