AtCoder Beginner Contest 235 E 問題 MST+1

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

重み付き連結無向グラフ $G=(V,E,C)$ が与えられる. ただし,

$V=\{1,2, \dots, N\}$
$E=\{a_1 b_1, \dots, a_M b_M\}$
$C(a_i b_i):=c_i$

である.

以下の質問に $Q$ 回答えよ.

$e_q=u_q v_q$ とする. 以下で構成される重み付き無向グラフ $G+e_q=(V, E \coprod \{e_q\}, C')$ の最小全域木に辺 $e_q$ は含まれているか? ただし,

$C'(e)=\begin{cases} w_q && (e=e_q) \\ C(e) && (e \in E) \end{cases}$

とする.

ここで, 以下のことが証明できる.

互いに辺の重みが異なる重み付き連結無向グラフにおいて, 最小全域木は一意に存在する.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$1 \leq a_i,b_i \leq N$
$1 \leq c_i \leq 10^9$
$G$ は連結
$G$ の辺の重みは全て異なる.
$1 \leq Q \leq 2 \times 10^5$
$1 \leq u_q, v_q \leq N$
$1 \leq w_q \leq 10^9$
$w_q$ の辺の重みは $G$ にあるどの辺の重みとも異なる.

解法

グラフ $G$ の最小全域木を $T$ とする. ここで, $T$ に含まれない辺については $G+e_q$ についても最小全域木に含まれることは無いので, 取り除いても構わない.

よって, 問題は $T+e_q$ の最小全域木に $e_q$ が含まれるか? という問題になる.

ここで, $T$ は木なので, $T+e_q$ はちょうど $1$ つのサイクルを持つ連結グラフ (通称: なもりグラフ) になるしかも, そのサイクルは辺 $e_q$ と $u_q, v_q$ Path をあわせたものになる. また, なもりグラフにおいて, 全域木から取り除かれるのはただ $1$ 辺であり, その辺はサイクルを成す辺である.

そして, 最小性を保つためには, そのサイクルを成す辺のうち, 重みが最大であるような辺を取り除くべきである. よって, 各問題は以下を解くことになる.

$T$ において, $u_q, v_q$ Path を構成する辺の重みの 最大値 を $h_q$ とする. このとき, $h_q \gt w_q$ であるか?

よって, Kruskal によって, 以下のアルゴリズムによって, $e_q$ について解くことができる.

そして, 以下は同値である.

$h_q \gt w_q$
$T$ において, 重みが $w_q$ 未満の辺だけを残したグラフ $T'$ において, $u_q, v_q$ は非連結である.

以上から, 以下のようなアルゴリズムを用いて, $Q$ 問をまとめて処理できる.

空グラフ $S=(V, \emptyset)$ を用意する.
$T$ の辺を $f_1, \dots, f_{N-1}$ とする.
について, 辺の重みが小さい順に以下を行う. ただし, 操作の対象の辺をとする.
- $e=f_j$ となる $j$ が存在する場合, $S$ に辺 $e$ を加える.
- $e=e_q$ となる $q$ が存在する場合, $S$ において, $u_q, v_q$ が非連結ならば, $q$ 問目は肯定的であり, 連結ならば否定的である.