2007/Contest/東京大会

Problem F : Slim Span †

問題概要 †

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

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

解法 †

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

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

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

議論・その他 †

ファイルを添付する †

mikurube_F.cpp