Problem F : Slim Span †問題概要 †無向グラフに対する、ある種の全域木 (Spanning Tree) を求める。 最小全域木 (Minimum Spanning Tree) と異なり、求めるのはその全域木に含まれる「重み最小の枝」と「重み最大の枝」の重みの差が最小であるような全域木である。 (三廻部; Nov 11, 2007) 解法 †全域木を求めるのに使う枝の重みの最小値 L を動かし、各 L に対して最小全域木を求める。 計算量は O(|E|^2) になる。 さらに効率のよい解法が存在するかもしれないが未確認。 (三廻部; Nov 11, 2007) 議論・その他 †ファイルを添付する †![]() |