ABC 352 E — Clique Connect

考察

集合 K_i 内へ重み C_i の clique を張ると辺数は二乗になるが、同じ重みの clique 内では一頂点を中心とする K_i−1 本だけで全頂点を同重み以下で連結できる。Kruskal 法では、ある辺の両端がその辺以下の重みの別 path で既に結ばれるなら、その辺を候補から除いても MST 重みは変わらない。star path は二辺かかっても MST の目的は辺数でなく重み総和であり、cycle property により同重み clique 辺を削除できる。全候補処理後に DSU component が一つでなければ、元の全 clique graph でも連結不能なので −1 である。

採用する候補: 各 clique を任意の代表と他頂点を結ぶ star K_i−1 辺へ縮約し、全 star 辺へ Kruskal 法を適用する。

削除した clique 辺は同じ重みの star path で代替でき、候補辺総数が ΣK_i に落ちる。

棄却する候補: 各集合内の全頂点対に辺を生成して通常の Kruskal 法を行う。

一集合 K_i=N のとき Θ(N²) 辺となり、ΣK_i≤4×10^5 という入力サイズ保証を活かせない。

各操作 i について A_{i,1} と A_{i,j}(j≥2) の辺 (C_i) だけを生成する。重み昇順に sort し、DSU で異 component を結ぶ辺の重みを加算する。採用辺が N−1 本なら総和、そうでなければ −1 を出す。

典型の発動条件

密な同重み clique の sparse certificate

発動条件: 暗黙に追加される完全グラフの全辺が同じ重みで、連結性だけが重要なとき。

任意 spanning tree だけ残し、同重み path を代替証明にする。

Kruskal 法と cycle property

発動条件: 辺候補を安全に削減して MST を求めたいとき。

辺以下の重みで端点を結ぶ別 path がある辺を除外する。

問題固有の要素

clique の完全な隣接情報は不要で、MST に必要な「同コストで集合内を連結できる証明書」は star で十分である。

別の問題へ持ち帰る視点: 暗黙 dense graph では、目的関数が保持される sparse certificate をまず探す。

正当性

同cost cliqueを同cost starへ変えても各閾値の連結成分が同じ。MSTのKruskal選択数は各重み閾値の連結性で決まるため最小costも不変。生成starのMSTを得れば元cliqueでも同cost接続を実現できる。

実装上の注意

  • star の中心は集合内ならどれでもよく、同重み辺の sort 順は任意。総重みは最大10^9(N−1)なので 64 bit を使う。

復習の核

  • 「二辺の代替だから高くなる」と誤解せず、Kruskal の時点で同重み連結になっていることを考える。縮約後の連結性も確認する。

計算量と制約

時間

N頂点、操作M、所属総数L=ΣK_i。生成辺O(L)、Kruskal O(L log L+Lα(N))。

空間

star辺とDSU O(N+L)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq M \leq 2 \times 10^5; 2 \leq K_i \leq N; \sum_{i=1}^{M} K_i \leq 4 \times 10^5; 1 \leq A_{i,1} < A_{i,2} < \dots < A_{i,K_i} \leq N; 1 \leq C_i \leq 10^9; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Clique Connect の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: cut・cycle性質から最適全域木を構成する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 最小・最大全域木とcut・cycle性質

    補助タグ: DSUによる連結成分管理・縮約

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

    学習の位置

    体系上の位置: cut・cycle性質から最適全域木を構成する

    • cut・cycle性質で辺の安全性を証明し、Kruskal法または同値な選択で最小・最大全域木を構成できる。

    先に読む単元:

    • DSUによる連結成分管理・縮約 — 辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 交換論から選択順を導く — 局所選択を交換論で正当化し、候補を安全に確定できる順序を導く。

    この解説で扱わないこと:

    • 任意の全域木を一つ構成するだけの探索、および辺重みを最適化しない連結成分管理。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題