JAG Domestic 2013 Sinking islands
いやー。盛大にバグらせた。
辛いね。
考察
無駄な橋はかけたくないです。
なので、最初っからこれ以上かける必要のないような橋のかけ方をします。
説明が何とも難しいところですが...
ある島を沈ませたとき、残った島が連結にならなかったらそこで計画は終了するので、島が連結を保てるぎりぎりまで島を沈ませていきます。その状態で最小全域木を作ります。
その後今度はまだ連結になっていない島の中で逆順に島を見ていき、くっつけていくといい感じになります。
まあ、これは意外と早めに気が付くのですが。
同時に沈んだ時の処理等、なかなかバグらせやすいところが満載です。
(特に最後が複数沈むときに私のはダメだったっぽい)(よい書き方ないかなあ?)
えー、ちゃんと詰めてから実装しましょうね。
連結に関してはUFがやっぱり楽かな~。