🌳
[ABC235 E] MST + 1
クラスカル法の応用問題。
問題文を理解する
解答から逆算すると、
- 最小全域木を作る上でクエリの辺は役に立つか？
と聞かれている。
考え方
もし、グラフが 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] 混ぜない方法
こちらの解説によると、いきなり元のグラフを一気に作ってから、何かする方法もあるらしいので、わかったら書く。
Discussion