えでもこれじゃあ時刻25で2の島が沈んだときに島7-9にリンク張らないとまずいのでは?と思ったけど、この場合は,新たに橋を架けることで,まだ沈んでいない島々の間で移動経路が確保できるようにする.どのように橋を架けても移動経路が確保できなくなった場合は,それ以上の橋の建設は行わない.これは「全域木が構成できないと分かったらそれ以上リンクを張らない」ということだった。そこで全域木を構成できない一番早い時刻を記録しておき、そこまではあらかじめ一緒くたにして最小全域木を構成し、そこから前に遡りながら島を追加し、最小全域木を構成することにした。この操作は一般化できるので、なお,現時点で既に移動経路を確保するように橋を架ける事が出来ない場合は,橋の建設は一切行わない.これについて気にする必要はなくなる。}これが「あらかじめ一緒くたにして」いる操作になる(降順に座圧してます)。あとは後ろから最小全域木を構成している。座標圧縮はソートで十分だとは思うけど、こちらのほうが実装が楽に感じた。あと少しで諦めて解説を見るところだった...。サンプルに助けられてしまったなあ。(3)はてなブログをはじめよう!arukukaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。