2002/Contest/世界大会

Problem A : Building Bridges

問題概要

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

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

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

解法

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

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

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

議論・その他

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

ファイルを添付する

filemikurube_a.c 577件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filemikurube_a.c 577件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:50 (2995d)