AOJ2511 Sinking islands (JAG Domestic 2013 D)
時間を逆から辿り、連結であれば最小全域木を構成して、状態を保存する。ただし、遡る過程で連結でなくなった場合には状態をリセットする。
連結でなくなったときに建設を止めるというところの認識を間違っていて、後々連結になったら建設を再開すると考えていてバグを産んだ。しかし読み直してみても若干問題分が曖昧だと思うので、そこを考えなければ致命的なバグはなくて一時間程度で解けていたので悪くはないと思う。プリム法は難しくはないが実装に慣れていないので少し遅くなってしまったし、簡易版なので計算量が少し多いものを実装した。今回は制約が緩かったが、速い版が必要になっても対応できるようにしておきたい。
