コスト0辺のテクニック - Senの競技プログラミング備忘録

　この記事は、競技プログラミングでよくあるグラフの問題で、愚直に問題文の指示通りやると辺の数があまりにも多くなりすぎるようなものに対して、コスト0の辺をうまく利用することで辺の数のオーダーを落とす者である。
　性質上、すべてのものに適応できるわけではないが、問題を解く際の参考にはなるはずである。
　ここで、今まで僕が見たことがあるコスト０辺をうまく利用するテクニックを並べる。
　ちなみに心なしか、コスト0辺でオーダーをうまく落とせるのは対象の頂点計nこの間に互いに行きかうことができる、 $_n C _k$ 本の辺を張るパターンが多い。

ターミナル駅方式

atcoder.jp

この問題では、どう考えても、(今いる駅, 直前に乗った電車の会社)とそれに類似してるものを頂点にして解くしかない。(最短経路問題は、頂点に情報を持たせるには次元拡張しかないはず)

しかし、愚直に辺を次のように張ると、辺の本数が $O(N^2)$ となる。赤い辺は乗り換えを表してる。

f:id:Sen_comp:20191110152514p:plain

しかし、次のようなターミナル方式にすれば、辺の数は駅1つあたり $O(N)$ 本に抑えられる。改札頂点という頂点を駅ごとに設けて、そこですべての行き交いをまとめるテクニックである。

f:id:Sen_comp:20191110153210p:plain

ちなみにこの問題ではこの操作を行っても、一見辺の数は $O(NM)$ (一つの駅ですべての線路が集まってる)になるが、もともとの行動可能の鉄道はM本で、1本につき多くても2つの駅(駅内で同じ会社があるならばさらに減る)にのみ関わるので、辺の数は $O(M)$ になる。
実装する際は、頂点の番号についてはpairの連想配列で行った。