お題箱より。
問題概要
頂点の無向完全グラフがある。このグラフの辺のうち、指定される
本の辺の重みは
であり、それ以外の辺の重みは全て
である。
このグラフの最小全域木の重み合計を求めよ。
制約
解法
クラスカル法のアルゴリズムより、まずはコスト の辺で連結にできる頂点を全て連結にしてしまい、それから残ったものをコスト
の辺で連結にすれば良いです。ただコスト
の辺は非常に多いので1つ1つ処理することはできません。
頂点数も辺数も非常に多いケース、例えば である場合を考えましょう。このときコスト
の辺は「スカスカ」です。より具体的には、コスト
の辺だけで考えた次数の合計が
なので、1頂点あたり平均で
本しかコスト
の辺が繋がっていないことになります。これは
である場合たったの
本です。
つまりコスト の辺が最も少ない頂点を1つ選んで
とすると、
に繋がっているコスト
の辺は
本以下です。ということは頂点
とコスト
の辺で繋がっていない(つまり、コスト
の辺で繋がっている)ような頂点が大量にあって、それらはノーコストで連結にすることができます。こうすると連結成分の個数が一気に減って、具体的には
個以下になります。
こうなると、既に連結になった頂点同士の辺はもう見る必要がありません。あとは頂点 と連結にできなかった
個以下の頂点それぞれについて、「相手の
個の頂点を全て試してコスト
の辺があれば連結にする」という処理をすれば、コスト
の辺だけでできる連結成分が得られます。あとは全頂点を連結にするのに足りない分、つまり連結成分の個数から
を引いたものが答えになります。
上記の手順は結局、前半は頂点 に、後半は
個以下の頂点について「相手の
個の頂点を全て試してコスト
の辺があれば連結にする」という処理をしていることになります。そのため全体計算量は
と評価できます。ここで
はアッカーマン関数の逆関数(Union-Findの操作計算量)です。