2002/Contest/世界大会/Problem A

Problem A : Building Bridges †

格子状の街にビルを建て、ビルの間に橋を架ける。一つの格子がビルの一単位、角が接している格子は同じビルとみなす。橋はビルの四隅から格子の線に沿ってのみ架けられる。

このとき、全てのビルをできるだけ少ない橋の数で繋ぐための、橋の数と橋の総距離を求める。橋の数が同じ架け方の中では、橋の総距離が短いものを選ぶ。

接続できないグループが出来てしまう場合は、そのグループの数も求める。

橋の長さを重みとした最小全域木 (Minimum Spanning Tree) 問題に帰結。

橋の数は自動的に最小、かつ、出来るだけ接続、になるはずなので、単純に長さを最小にすればいい。

"disconnected groups" は (島の数) - (橋の数) で。 (三廻部; Mar 20, 2004)

一時間半。もっとかかってしまうかと思って冷や冷や。十分遅いんだけど。
去年は何で解けなかったのかなあ。確か去年と同じアプローチなので、これも間違ってるのかも...。
どうでもいいけど、微妙なソース。後で書きなおそ。 (三廻部; Mar 20, 2004)