AOJ 2511 : 沈みゆく島

Sinking islands | Aizu Online Judge

一番最初のサンプルケースを見ると、
沈む時刻が最後の方から最小全域木を構成していくと良さそう
(座圧して、時刻が同じものはグルーピングしておく)。

一番最初に沈むところまで終えて、
Union-Findが全部同じ親を持つかチェックして
ダメだったら0を出せばいいのかな。

しかしこれでは4番目のサンプルケースが合わない(金額が高くついてしまった)。
何故だ…。ふと普通に最小全域木にしたらコストはどうなるのだろうと思って
やってみたらサンプルと一致する。ホンマか。

図解してみる。

f:id:arukuka:20170617082237p:plain

えでもこれじゃあ時刻25で2の島が沈んだときに
島7-9にリンク張らないとまずいのでは?
と思ったけど、

この場合は,新たに橋を架けることで,まだ沈んでいない島々の間で移動経路が確保できるようにする.
どのように橋を架けても移動経路が確保できなくなった場合は,それ以上の橋の建設は行わない.

これは「全域木が構成できないと分かったらそれ以上リンクを張らない」ということだった。

そこで全域木を構成できない一番早い時刻を記録しておき、
そこまではあらかじめ一緒くたにして最小全域木を構成し、
そこから前に遡りながら島を追加し、最小全域木を構成することにした。

この操作は一般化できるので、

なお,現時点で既に移動経路を確保するように橋を架ける事が出来ない場合は,橋の建設は一切行わない.

これについて気にする必要はなくなる。

AC。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2375641#1

関数calが「全域木を構成できない一番早い時刻」のindexを返し、

      for (int i = 0; i < s; ++i) {
        List<Integer> comer = t.get(i);
        list.addAll(comer);
        added.addAll(comer);
      }

これが「あらかじめ一緒くたにして」いる操作になる
(降順に座圧してます)。
あとは後ろから最小全域木を構成している。

座標圧縮はソートで十分だとは思うけど、
こちらのほうが実装が楽に感じた。


あと少しで諦めて解説を見るところだった…。
しかしサンプルに助けられてしまったなあ。