phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

ARC093 E. Bichrome Spanning Tree

問題

N頂点M辺の重み付き無向グラフGと整数Xが与えられる。
このグラフGの各辺を白か黒で塗りたいが、以下の条件を満たす塗りかたが何通りあるかmod 10^9+7で求めたい。
条件「白辺と黒辺どちらも含む全域木が存在し、そのような全域木のうち、辺の重みの和が最小のものの和はX」

制約

  • 1 <= N <= 1,000
  • 1 <= M <= 2,000
  • 1 <= 辺の重み <= 10^9, 辺の重みはすべて整数
  • 1 <= X <= 10^12

解法

そもそも題意を正しく読み取れてなかった・・・大雑把に解法をまとめておく、、

題意

入力例2の例で、全部の塗りかたを列挙して確認してみる。
f:id:phyllo_algo:20180327004825p:plain
辺の塗りかたは8通り考えられ、それぞれの塗り方で「白辺と黒辺どちらも含む全域木(各枠の真ん中)」と「その全域木の中で、辺の重みの和の最小値(各枠の右側)」を図示。
X=2の場合は答えが4個、X=3の場合は答えが2個になっているのが確認できる。

アプローチ

おおよそ以下のような流れで考えると良い?

  • 「全域木の辺の和の最小値がx」になるためには、(x-1)以下になる全域木で使われるような辺すべてが同じ色になっていないといけないことに気付く
  • そのような場合での辺の色の塗り分け方をf()として考え、そこから答えを求める
  • f()の計算式(塗り分け方の式)と、計算に必要な要素を求める


上の図で、X=3の場合を考えてみる。
最小のものが2になってしまわないために、「全域木の辺の和が2になるような全域木」に使われるすべての辺が同じ色になっていないといけないことがわかる。
したがって、Xがもっと大きい場合を考えると、「全域木の辺の和がX-1以下になる全域木に使われる辺がすべて同じ色になっている」必要がある。


そこで、「全域木の辺の和がX-1以下になる全域木に使われる辺がすべて同じ色になっている」ような塗り方が何通りか?を表すf(X-1)を計算することを目指す。
このf(x)が求められれば、「f(X)とf(X-1)の差分」が題意を満たす塗りかたの通り数になる。


上図で考えると、f(2)は「全域木の辺の和が2以下になる全域木に使われる辺」というのは1-2と2-3の辺で、それが同じ色になっているような塗りかたは、「1-2と2-3の辺の色」と「それ以外の辺1-3の辺の色」がそれぞれ黒または白で、すべての頂点が同じ色になる2通りを引いた「2^1 * 2^1 - 2 = 2通り」になる。(f(2)=2)
また、f(3)は「全域木の辺の和が3以下になる全域木に使われる辺」は1-2と2-3と1-3すべての辺で、それがすべて同じ色になっているような塗りかたは、同様にして「2^1 * 2^0 - 2 = 0通り」になる。(f(3)=0)
f(1)を考えてみると、そのような辺は存在しないので「2^0 * 2^3 - 2 = 6」。(f(1)=6)
f(4)を考えてみると、すべての辺が該当するので、f(3)と同じで「0」。(f(4)=0)
X=3のケースでは、f(3)=0とf(2)=2の差分で「f(2)-f(3)=2」が答えになる。


上記の考察からf(x)の求め方を考えてみると、同じ色にしないといけない辺の数がa本ならば、どんな色で塗ってもいい辺の数は(M-a)本なので、aが1本以上なら「f(x) = 2^1 * 2^(M-a) - 2」、aが0本なら「f(x) = 2^0 * 2^M - 2」で求められる。


最後に、上記のa本は「全域木の辺の和がx以下になる全域木に使われている辺」のことで、これを効率的に求める必要がある。
例えば、一つのMSTを求めてその重みがAだったとすると、そのMSTに使われた辺は「全域木の辺の和がA以下になる全域木に使われている辺」であることがわかる。
使われなかった辺については、もしかしたらその辺を利用しても全域木の辺の和がAになる全域木を作れるかもしれない(入力例1)し、そうでないかもしれない。


ということで、ある辺eがどのタイミングで全域木に使われる辺に選ばれることになるか?を考える。
これは、「その辺eを必ず使ってMSTを作った場合、そのMSTの辺の重みの和がB」というのを求めてあげれば、「全域木の辺の和がB以下になる全域木に使われる辺」ということが言えるので、その辺eはBのとき同じ色に塗る必要がでてくるということがわかる。
これは、最初に必ず使いたい辺を選んで、残りの辺は普通にクラスカル法を適用すれば求められる。
したがって、すべての辺eについてこの値Bがわかっていれば、f(x)で必要な「a本」が求められる。


計算量は、各辺についてその辺を必ず含むMSTを求めるところが一番重くて、各辺についてpriority_queueとUnionFindを使ってだいたいO(M * MlogM)ぐらい。