Educational Codeforces Round 3 E. Minimum spanning tree for each edge

ダブリング練習用の問題。HL 分解でもいける。

問題文

http://codeforces.com/contest/609/problem/E

問題概要

重み付き無向グラフが与えられるので、i 番目の辺を使った最小全域木の重みを、すべての i に対して求めよという問題。

最大の頂点数は 2・105、最大の辺の数は 2・105、最大の辺の重みは 109

解法

i 番目の辺を使った最小全域木は以下の手順で構成できる。

  1. 最小全域木を構成する
  2. i 番目の辺を追加する
  3. このときできる閉路にある最大の重みの辺を削除する

それぞれ図で説明する。

1. 使う辺の制約なしで最小全域木を構成する

f:id:pekempey:20151220030013p:plain

2. i 番目の辺を追加する

f:id:pekempey:20151220025315p:plain

3. 閉路の中にある最大の重みの辺を削除する

f:id:pekempey:20151220030433p:plain

したがって、この問題は u-v 間の最大の重みを求めるクエリ問題として見ることができる。 これはダブリングや HL 分解を使えばいい。

ダブリング

u-v 間クエリは u-LCA(u,v) と v-LCA(u,v) の2つのクエリに分解して計算できるので、祖先間クエリに答えられれば u-v 間クエリも答えられる。 祖先間クエリは、2i 個上との間の最大の重みを前計算しておくことで O(log n) で答えられる。

手持ちの LCA のライブラリに max の機能を付け足す形で実装した。 一度でも実装した経験があればそんなに大変な作業ではなさそう。

最大実行時間は 576 ms 。

Educational Codeforces Round 3 E. Minimum spanning ...

HL 分解

辺に情報が乗っている場合は、辺の情報を下の頂点に移せばいい。 u-v 間クエリを行う際は LCA(u, v) を含めないように注意。

分量は多いけど RMQ も HL 分解も貼るだけなので、自分で実装するのは main 関数内ぐらい。 LCA(u, v) を除外するのが面倒だけど、除外するいい方法ないかな。

最大実行時間は 624 ms。ダブリングより定数が重いかと思ったけど大して変わらなかった。

Educational Codeforces Round 3 E. Minimum spanning ...

LCA 以外で初めてダブリングを書いた。 結局コンテスト中はバグが取りきれなかったけど、ダブリングの練習が出来たので満足。