🌳

[ABC235 E] MST + 1

2024/02/16に公開

Ruby

クラスカル法の応用問題。

問題文を理解する

解答から逆算すると、

最小全域木を作る上でクエリの辺は役に立つか？

と聞かれている。

考え方

もし、グラフが A-C-B でクエリにコストが低い A-B の辺があり、今よりもコストが下げられそうなので A-B の辺を繋げたとする。すると A-C C-B の辺のどちらかは不要になるはず。不要であれば削除しなければならなくて、グラフで「削除」ときたら「作り直す」と言い直す。つまり、作りながらクエリの辺が役に立つかを確認する。

また最小全域木はコストが低い順に作るので、グラフとクエリの辺を「コストが低い順に選択」する。

そしてクエリの辺の番が来たら「その辺が役に立つか？」を調べる。具体的には「非連結か？」を確認する。

そこで注意したいのが、その辺が役に立つからといって、それを使って森を作ってはいけない。元のグラフの構造が変わってしまい、その後のクエリの判定がおかしくなってしまう。あくまで「その辺が役に立つか？」を調べるだけである。

具体例

↓ 元のグラフを構成する辺の一覧と、

種類	辺	コスト
グラフ	A-B	2

↓ クエリの一覧を、

種類	辺	コスト
クエリ1	A-B	3
クエリ2	A-B	1

↓ 混ぜてコストで並び換えると、

種類	辺	コスト
クエリ2	A-B	1
グラフ	A-B	2
クエリ1	A-B	3

になり、上から順に選択して、クエリなら役に立つか確認し、グラフであれば単に森を作ると、

種類	辺	コスト	単に作る	役に経つか確認
クエリ2	A-B	1		○
グラフ	A-B	2	作る
クエリ1	A-B	3		× (すでに A と B は繋がっていたため)

答えは ○ × つまり、ひと目 Yes No だけど、クエリはもともとクエリ1 クエリ2 の順で並んでいたので No Yes が答えになる。

コード (AC)

N, M, Q = gets.split.collect(&:to_i)                  # => [5, 6, 3]
ABC = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 2, 2], [2, 3, 3], [1, 3, 6], [2, 4, 5], [4, 5, 9], [3, 5, 8]]
UVW = Q.times.collect { gets.split.collect(&:to_i) }  # => [[1, 3, 1], [3, 4, 7], [3, 5, 7]]

edges = ABC + UVW                                     # => [[1, 2, 2], [2, 3, 3], [1, 3, 6], [2, 4, 5], [4, 5, 9], [3, 5, 8], [1, 3, 1], [3, 4, 7], [3, 5, 7]]
edges = edges.collect.with_index { |e, i| [*e, i] }   # => [[1, 2, 2, 0], [2, 3, 3, 1], [1, 3, 6, 2], [2, 4, 5, 3], [4, 5, 9, 4], [3, 5, 8, 5], [1, 3, 1, 6], [3, 4, 7, 7], [3, 5, 7, 8]]
edges = edges.sort_by { |_, _, w, _| w }              # => [[1, 3, 1, 6], [1, 2, 2, 0], [2, 3, 3, 1], [2, 4, 5, 3], [1, 3, 6, 2], [3, 5, 7, 8], [3, 4, 7, 7], [3, 5, 8, 5], [4, 5, 9, 4]]

ds = DisjointSet.new
ans = Array.new(Q)

edges.each do |*edge, _, i|
  i = i - M
  if i < 0
    ds.unite(*edge)
  else
    ans[i] = ds.different?(*edge)
  end
end

ans                                                   # => [true, false, true]
puts ans.collect { |e| e ? "Yes" : "No" }

[TODO] 混ぜない方法

こちらの解説によると、いきなり元のグラフを一気に作ってから、何かする方法もあるらしいので、わかったら書く。

問題文を理解する

考え方

具体例

コード (AC)

[TODO] 混ぜない方法

Discussion