Codeforces Round #599 (Div. 1) B. 0-1 MST

お題箱より。

Problem - B - Codeforces

問題概要

$n$ 頂点の無向完全グラフがある。このグラフの辺のうち、指定される $m$ 本の辺の重みは $1$ であり、それ以外の辺の重みは全て $0$ である。

このグラフの最小全域木の重み合計を求めよ。

制約

$1 \le n \le 10^{5}$
$0 \le m \le \min(\frac{n(n-1)}{2}, 10^{5})$

解法

クラスカル法のアルゴリズムより、まずはコスト $0$ の辺で連結にできる頂点を全て連結にしてしまい、それから残ったものをコスト $1$ の辺で連結にすれば良いです。ただコスト $0$ の辺は非常に多いので1つ1つ処理することはできません。

頂点数も辺数も非常に多いケース、例えば $n = m = 10^{5}$ である場合を考えましょう。このときコスト $1$ の辺は「スカスカ」です。より具体的には、コスト $1$ の辺だけで考えた次数の合計が $2m$ なので、1頂点あたり平均で $\frac{2m}{n}$ 本しかコスト $1$ の辺が繋がっていないことになります。これは $n=m=10^{5}$ である場合たったの $2$ 本です。

つまりコスト $1$ の辺が最も少ない頂点を1つ選んで $v$ とすると、 $v$ に繋がっているコスト $1$ の辺は $\frac{2m}{n}$ 本以下です。ということは頂点 $v$ とコスト $1$ の辺で繋がっていない（つまり、コスト $0$ の辺で繋がっている）ような頂点が大量にあって、それらはノーコストで連結にすることができます。こうすると連結成分の個数が一気に減って、具体的には $\frac{2m}{n}+1$ 個以下になります。

f:id:betrue12:20200224164852p:plain

こうなると、既に連結になった頂点同士の辺はもう見る必要がありません。あとは頂点 $v$ と連結にできなかった $\frac{2m}{n}$ 個以下の頂点それぞれについて、「相手の $n-1$ 個の頂点を全て試してコスト $0$ の辺があれば連結にする」という処理をすれば、コスト $0$ の辺だけでできる連結成分が得られます。あとは全頂点を連結にするのに足りない分、つまり連結成分の個数から $1$ を引いたものが答えになります。

上記の手順は結局、前半は頂点 $v$ に、後半は $\frac{2m}{n}$ 個以下の頂点について「相手の $n-1$ 個の頂点を全て試してコスト $0$ の辺があれば連結にする」という処理をしていることになります。そのため全体計算量は $O( (n+m)\alpha(n) )$ と評価できます。ここで $\alpha(n)$ はアッカーマン関数の逆関数（Union-Findの操作計算量）です。