🌳
[ABC352 E] Clique Connect
いじわる最小全域木問題。
問題を要約する
- 部分集合のすべてに辺を貼る
- 完成したグラフは連結か？
- それなら MST のコストは？
考え方
部分集合のすべてに辺を貼れと言われてその通りにしてはいけない。続いて MST を作るところまで含めて考えると、いきなり MST を作るのが正しい。
たとえば 1 2 3 で 1-2-3 と繋がっていれば、
もう充分である。
まで繋いでいると TLE になる。
- 連結してればよい →
N - 1 - 完全グラフ →
N * (N - 1) / 2
ただ、いきなり MST を作るにしても辺の最小コストがまだ求まっていないのでないかと考えたが、それは「部分集合＋コスト」の入力を最初にコストで並び換えておけばよいだけだった。
自力解答 (TLE)
N, M = gets.split.collect(&:to_i)
KCA = M.times.collect { [*gets.split.collect(&:to_i), gets.split.collect(&:to_i)] }
ds = DisjointSet.new(1..N)
edges = Hash.new(Float::INFINITY)
KCA.each do |_, cost, list|
list.combination(2) do |edge| # ← 部分的に完全グラフ化しようとしている
ds.unite(*edge)
if cost < edges[edge]
edges[edge] = cost
end
end
end
total = 0
ds = DisjointSet.new(1..N)
edges = edges.sort_by { |_, cost| cost }
edges.each do |edge, cost|
if ds.different?(*edge)
total += cost
end
ds.unite(*edge)
end
p ds.tree_count == 1 ? total : -1 # => 9
考え方が間違っているもののコンテスト後に combination を each_cons に変更してみたら 1841 ms でギリ通った。
解説の模範解答 (AC)
1293 ms
N, M = gets.split.collect(&:to_i)
KCA = M.times.collect { [*gets.split.collect(&:to_i), gets.split.collect(&:to_i)] }
total = 0
ds = DisjointSet.new(1..N)
KCA = KCA.sort_by { |_, cost, _| cost }
KCA.each do |_, cost, list|
list.each_cons(2) do |edge|
if ds.different?(*edge)
total += cost
end
ds.unite(*edge)
end
end
p ds.tree_count == 1 ? total : -1 # => 9
ただのクラスカル法だった。
Discussion