2007/Contest/東京大会

Problem F : Slim Span

問題概要

無向グラフに対する、ある種の全域木 (Spanning Tree) を求める。

最小全域木 (Minimum Spanning Tree) と異なり、求めるのはその全域木に含まれる「重み最小の枝」と「重み最大の枝」の重みの差が最小であるような全域木である。 (三廻部; Nov 11, 2007)

解法

全域木を求めるのに使う枝の重みの最小値 L を動かし、各 L に対して最小全域木を求める。
(これで求める全域木が求まることの証明は気が向いたら記す)

計算量は O(|E|^2) になる。

さらに効率のよい解法が存在するかもしれないが未確認。 (三廻部; Nov 11, 2007)

議論・その他


ファイルを添付する

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

管理者パスワード:

添付ファイル: filemikurube_F.cpp 1803件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:39 (5374d)