Sensor network (UVa Live Archive Europe Southwestern 2010)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2961

問題

n頂点のグラフが与えられる。全域木の中で使ってる辺のコストの最大値-最小値の最小値を求めよ。
2<=n<=350

解法

辺を重み順にソートして順番に辺を付け加える。もしも閉路ができてしまったら、閉路の中で一番重みの小さい辺を削除する。閉路の検出をdfsでやれば全体のオーダーはO(nm)になるらしい。link cut treeを使って辺の削除ができるUnionFindを使えばO(mlogn)でできるらしい。