AtCoder Regular Contest 083 D. Restoring Road Network

結構面白かった。

 

問題

読んで: D - Restoring Road Network

 

解法

Warshall-Floyd法を考えれば、与えられたテーブルが条件を満たしているかは、Warshall-Floyd法内で行う更新を行っても値が変化しなければ良いことが分かるので、こっちは自明。

問題はグラフの復元で、初め、incrementalに、つまり、辺が1つもない状態から、長さが最小の辺から順に、追加するか決めていこうとしたんだけど、毎回全点間最短経路の更新にΘ(N^2)掛かりそうで、辺はΘ(N^2)個あることを考えるとΘ(N^4)になるなあと思っていた。

ここで面白いのは、逆にdecrementalに、つまり全ての頂点対間に、最短経路長と同じ辺が張ってあるようなグラフを元にして、そこから長さ最大の辺から順に消していくことを考えるとうまくいく。

辺を追加することによって最短経路が更新され得る点対の個数はO(N^2)であり、「辺を追加すべきか」の判定に必要な情報を保持しておくにはΘ(N^2)掛かってしまうが、「辺(u, v)を削除すべきか」を考慮する際に必要な情報は常に変わらない。しかも、見るべきはu, v間の最短経路長が変わるかどうかのみであって、これはO(N)で判定できる。これもWarshall-Floyd法を想像すればすぐ分かる。