E - Erasing Verticles 2

とり得る値の最小値を求める問題では、二分探索できないか疑います。今回の問題の場合、

という問題を考えると、あるコスト以下は全て可能で、それより大きいコストは全て不可能という境界が存在することが言えます。

後は、コスト $X$ を定めたときに、この問題について高速に判定できればよいです。

判定方法について考えます。

コスト $X$ 以下の頂点があればとにかく消した方がよいです。なぜなら、そうすることでその頂点と隣接する頂点のコストを減らすことができるからです。

というわけで、以下の貪欲法が考えられます。

未削除の頂点のうち、コスト $X$ 以下の頂点を1つ選び、削除する。削除した頂点と隣接する頂点のコストを減らす。これを削除可能な頂点が無くなるまで繰り返す。

この貪欲法について、例えば、削除対象を毎回全頂点から選び出しているだけでも $O(N^2)$ になってしまいます。

ある頂点を削除した時、次に削除対象となる可能性があるのは、その頂点と隣接する頂点だけです。
従って、削除可能な頂点集合 $S$ を管理することで、以下のように処理できます。

頂点を1つも削除していない初期状態で、削除コストが $X$ 以下の頂点を $S$ に追加する。その後、 $S$ が空になるまで以下を繰り返す。

$S$ から頂点を1つ選び、削除する。
削除した頂点に隣接する頂点のコストを減らし、 $X$ 以下なら $S$ に追加する。

$S$ が空になった時点で、全ての頂点が削除されていれば、達成可能です。そうでないなら、不可能です。

この方法は、すべての頂点の $N$ 回の削除処理において、頂点を削除した時にその頂点から出る辺を1回ずつ辿るので、辺を辿るのは合計 $2M$ 回となります。
よって、 $O(N+M)$ です(多分)。

これにより、高速に判定できることがわかりました。

従って、初期状態でのコストの最大値を $C_{max}$ とすれば、元の問題を $O((N+M)log{C_{max}})$ で解くことができます。

コストが最大となるのは、おそらく全ての頂点に $10^9$ が書かれた場合の完全グラフだと思われます。
その場合でも $2\times 10^{14}$ は超えないはずなので、二分探索も十分高速です。

また、コストの下限は0になることに気をつけなければいけません(これに気づけず、コンテスト中にACできませんでした)。

geam1113’s diary