🌳
[ABC264 E] Blackout 2
発電所は一つでよいと気づけるか問題。
解き方
- 発電所を一つにする
- 削除しない電線だけを残したグラフを作る
- 逆から電線を作っていく
- その際に電気が通っている都市数を数える
例1でシミュレーション
都市の、
発電所を一つにまとめて、
削除しない電線(太線)だけを、
残し、
電線を逆から繋げていき、
| クエリ順 | 電線番号 | 電線 | 素集合森 | 電気が来ている都市数 |
|---|---|---|---|---|
| 2-3 4-6 | 1 | |||
| 6 | 6 | 1-6 | 2-3 4-6-1 | 2 |
| 5 | 1 | 4-6 | 2-3 4-6-1 | 2 |
| 4 | 9 | 1-6 | 2-3 4-6-1 | 2 |
| 3 | 7 | 3-6 | 2-3-4-6-1 | 4 |
| 2 | 4 | 2-6 | 2-3-4-6-1 | 4 |
| 1 | 2 | 5-6 | 2-3-4-6-1-5 | 5 |
電線を切ったことにすれば答えは 4 4 2 2 2 1 になる。
コード (AC)
N, M, E = gets.split.collect(&:to_i) # => [5, 5, 10]
UV = E.times.collect { gets.split.collect(&:to_i) } # => [[2, 3], [4, 10], [5, 10], [6, 9], [2, 9], [4, 8], [1, 7], [3, 6], [8, 10], [1, 8]]
Q = gets.to_i # => 6
Query = Q.times.collect { gets.to_i } # => [3, 5, 8, 10, 2, 7]
Query.collect!(&:pred) # => [2, 4, 7, 9, 1, 6]
QuerySet = Query.to_set # => #<Set: {2, 4, 7, 9, 1, 6}>
PowerPlant = N.next # => 6
edges = UV.collect { |e| e.collect { |e| [e, PowerPlant].min } } # => [[2, 3], [4, 6], [5, 6], [6, 6], [2, 6], [4, 6], [1, 6], [3, 6], [6, 6], [1, 6]]
default_edges = edges.reject.with_index { |_, i| QuerySet.include?(i) } # => [[2, 3], [6, 6], [4, 6], [6, 6]]
ans = []
ds = DisjointSet[default_edges] # => 親:{2=>3, 3=>3, 6=>6, 4=>6} 構図:{3=>[2, 3], 6=>[6, 4]} 節数:{3=>2, 6=>2} 木数:2 高さ:{3=>2, 6=>2}
Query.reverse_each do |i|
ans << ds.size(PowerPlant).pred # => [1], [1, 2], [1, 2, 2], [1, 2, 2, 2], [1, 2, 2, 2, 4], [1, 2, 2, 2, 4, 4]
ds.unite(*edges[i])
end
ans = ans.reverse # => [4, 4, 2, 2, 2, 1]
puts ans
Discussion