AOJ 2559 : Minimum Spanning Tree

データ構造 木 グラフ

Minimum Spanning Tree | Aizu Online Judge

問題概要

  • グラフが与えられます。
  • 辺iをグラフから取り除いた時にできる最小全域木のサイズを出力して下さい(0<=i<M)

解法

  • Kruskal + SegmentTree + HL分解 + SegmentTree
  • SegmentTreeと二回書いたのは用途が違うからです。
  • やりたいことは、まず最小全域木を作る。
  • できた木の各部分木について部分木に含まれる全ての"その部分木の外"に伸びてる辺の最小値を見つける。
  • というのをデータ構造を使って強引に高速化。
  • 250行っておい
ソースコード

感想

HL分解+seg木で初めて通した問題なので個人用のメモとしてあげました。

ほかの人のブログみたらもっとスマートな解法で実装していた。