3228 Gold Transportation

概要

100個の町とそれをつなぐ双方向のエッジがいくつかある．
すべての町に，発掘された金の量と，金をしまっておける量が設定されている．
すべての金をしまえるように，金を移動したい．
すべての金の移動パスの中で，一番離れているエッジの長さ，を最小化すると言う問題．

解法

見た瞬間，ワーシャルフロイド＋二分探索＋最大流だ！と思って，それでACをもらったんだけど，
もっといいやり方があっるみたい．
discussをチラ見するとタイトルに合併集(UnionFindの中国語版w)と書いてあるのを発見，ちょっと考えてみた．
UnionFindに，発掘された金を正，保存しておける金を負とした，和の値の配列を持たせておいて，uniteするときにこの値を合算するようにする．
与えられたエッジの集合を，priority_queueに突っ込んでおいて，安い枝の端点からuniteしてゆく．
このとき，すべての代表元について，和の値が0以下ならば，unionfind森の各木について，木の中で金を移動するだけでokな状態になっている．
こうなった瞬間の枝の重さが，全体の中の一番離れてる距離となる．
前の方法では，O(ALL-PAIR-SHORTEST + log(d) * MAXFLOW) = O(V^3 + log(d) * V^2 * E) (Floyd Warshall, Dinicを使うと)
unionfindを使った方法だと，O(SORT + V * UNITE) = O(ELogE + V * A(V)) 位になるのかな？
E=O(V)のとき，O(V^3*log(d))とO(Vlog(V))
E=O(V^2)のとき，O(V^5*log(d))とO(V^2*log(V^2))
速いし，距離にも依存しなくていい感じ☆