ABC 383 E — Sum of Max Matching

考察

pathの最大辺最小値f(x,y)は、重みw以下の辺だけを残したgraphでx,yが初めて連結になる閾値である。したがって辺を昇順に足すKruskal過程と一致する。成分を結ぶ重みwの時点で、片成分のA-tokenと他方のB-tokenはどの組もcost wで結べる。より後へ残すとcostは下がらないので、可能なだけ即座にpairにしてよい。成分には未使用A個数caと未使用B個数cbだけ持てばよく、実際のpairを復元する必要はない。二成分併合時はmin(ca_left,cb_right)+min(cb_left,ca_right)組を重みwで確定し、残数を新rootへ集約する。

採用する候補: 辺を重み昇順にDSUで併合し、成分内の未matching A/B個数を貪欲に相殺する

各token対の最小bottleneck値が成分の初結合時に確定し、交換論によりcross成分で作れるpairを即時に結んでも最適matchingを失わない。

棄却する候補: 各A_i,B_j間のminimax距離を個別に求めて二部matchingする

K^2個の距離を扱うだけで上限を超え、minimax距離の階層構造も利用していない。

辺を昇順sortし、各頂点のA,B出現回数でDSU成分countを初期化する。公式制約A_i≠B_jにより、一頂点に両種類は同居しない。異なる成分を辺wで結ぶたびcross方向のpair数だけwを答えへ加え、残countをmergeする。

各成分には高々一種類の未使用tokenが残る、という不変量でcrossの二項を使う。初期状態ではA_i≠B_jがこの性質を保証し、併合時に可能なだけ異種tokenを相殺すると性質を保つ。同じ頂点へ同種tokenが複数あることは許されるので、頂点の有無ではなく出現回数を保持する。

典型の発動条件

Kruskal reconstructionの閾値解釈

発動条件: path costが辺重みの最大値で、最小化したいとき。

辺を昇順追加した最初の連結時刻を二点間costとみなす。

DSU成分上の貪欲matching

発動条件: 成分間の全pairが同じ確定costを持ち、将来costが非減少なとき。

相補的tokenを併合時に可能なだけ相殺する。

問題固有の要素

minimax距離は通常の距離表でなく、重みthresholdごとの連結成分というultrametric的な階層で表せる。

別の問題へ持ち帰る視点: pair costが「初めて同じ成分になる時刻」なら、全pairを列挙せずcomponent aggregateだけをKruskal順に処理する。

正当性

公式制約A_i≠B_jから初期成分には高々一種類のtokenしかなく、cross相殺後もこの不変量が保たれる。bottleneck costはKruskalで初めて同成分になる重み。二成分の逆種tokenはその時点で全て同費用wで結べ、先送りしても費用は下がらない。最適matchingのpair交換で今cross pairを可能なだけ確定する最適を選べる。残種数だけで将来を決め成分mergeで厳密に管理する。

実装上の注意

公式制約A_i≠B_jで異種tokenの同居はない。同種の重複は個数として数える。辺重み昇順、同成分辺は無視する。merge前の逆種countからpair数を決め残数を新代表へ渡す。総costはtoken数×最大重みなので64bitにする。

復習の核

  • 小さいgraphで全pairのminimax距離をFloyd型に求め全permutation matchingと比較し、同重み辺順序や同一頂点のA/B重複でも答えが不変か確認する。

計算量と制約

時間

N頂点M辺、token数K。sort O(M log M)、DSU/count merge O((N+M+K)α(N))。

空間

DSU、辺、二種token count O(N+M+K)。

制約との対応

公式制約の確認範囲: Time limit: 2.5 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; N-1 \leq M \leq \min(\frac{N \times (N-1)}{2},2 \times 10^5); 1 \leq K \leq N; 1 \leq u_i<v_i \leq N (1 \leq i \leq M); 1 \leq w_i \leq 10^9; 1 \leq A_i,B_i \leq N (1 \leq i \leq K); The given graph is simple and connected.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sum of Max Matching の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Kruskal順の閾値DSU sweep

主題
  • Kruskal順の閾値DSU sweep: 同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: Kruskal順の閾値DSU sweep

    補助タグ: DSUによる連結成分管理・縮約 貪欲法と交換論

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

    学習の位置

    体系上の位置: Kruskal順の閾値DSU sweep

    • 同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題