2019年1月31日木曜日

ABC 061 D - Score Attack

ABC 061 D - Score Attack

最小全域木を求めるアルゴリズムはすべて負のコストを扱えるので、最大全域木を求めるのにも使える。このことを理解するためには、負辺を含む頂点数nnのグラフGGについて、各辺に大きな正の定数CCを足してすべて正のコストに変えたグラフGG'でMSTを求めることを考えてみればよい。GG'の全域木のコストは、GGの同じ全域木のコストKKに対して常にK+C(n1)K+C(n-1)になるから、GGGG'は同じMSTを持つことになる。したがって、正の重みについて正しく動くアルゴリズムは、一般のグラフについてもうまくいくのである。

プリム法は負辺があってもOKなのに、似たような動作をするダイクストラ法はだめなのはなぜかと言えば、「全域木は辺の数が一定(n1n-1)だが最短経路はそうではないから」ということになるだろう。逆に考えると、パスsts - tの辺数が一定とわかっている場合にはダイクストラが使えるということになる?(考えてみたけどあんまり意味無さそう)