🌳

[ABC218 E] Destruction

2024/02/10に公開

Ruby

辺を削除する問題。

問題文を理解する

0 個以上の辺を取り除こうとしています。
辺を取り除いたあともグラフが連結でなければならないとき〜

を、ひとことで言えば、

無駄な辺を削除したい

になり、加えて「辺を削除」は、

その辺を使わずに作る

に言い換える。

もう少しわかりやすく言えば「作る段階で、その辺を使わなくても連結を保てていたなら、その辺は不要だった」になる。

具体例

次のグラフの辺を A-B-C-A の順で作ったときの考え方。

辺	報酬	木	考え方
A-B	1	A-B	A と B を連結する
B-C	0	A-B-C	B と C を連結する
C-A	-1	A-B-C-A	C と A はすでに A-B-C でつながっていた

となるので3つめの辺 C-A はなくてもよい。ということは完成型から C-A を削除できるのでその報酬 -1 が答えになる。

edges = [["A", "B", 1], ["B", "C", 0], ["C", "A", -1]]
ds = DisjointSet.new
acc = 0
edges.each do |*ab, c|
  if ds.same?(*ab)
    acc += c  # => -1
  end
  ds.unite(*ab)
end
p acc         # => -1

報酬の最大化

ただし報酬は最大にしたい。それなら負の報酬は受け取らない方がよい。またグラフを見れば報酬がもっとも高い A-B を後回しにすれば A-B の辺を作らなくてすむため報酬 1 が貰えるのも想像がつく。

よって、

報酬の高い辺ほど後回しにする
- 報酬で昇順ソート
報酬がプラスになる辺を対象にする
- 報酬 > 0

を付け加える。

edges = [["A", "B", 1], ["B", "C", 0], ["C", "A", -1]]
edges = edges.sort_by { |*_, c| c }  # => [["C", "A", -1], ["B", "C", 0], ["A", "B", 1]]
ds = DisjointSet.new
acc = 0
edges.each do |*ab, c|
  if c.positive? && ds.same?(*ab)
    acc += c                         # => 1
  end
  ds.unite(*ab)
end
p acc                                # => 1

提出したコード (AC)

N, M = gets.split.collect(&:to_i)                       # => [4, 5]
edges = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 2, 1], [1, 3, 1], [1, 4, 1], [3, 2, 2], [4, 2, 2]]
edges = edges.sort_by { |*_, c| c }                     # => [[1, 2, 1], [1, 3, 1], [1, 4, 1], [3, 2, 2], [4, 2, 2]]
ds = DisjointSet.new
acc = 0
edges.each do |*ab, c|
  if c.positive? && ds.same?(*ab)
    acc += c                                            # => 2, 4
  end
  ds.unite(*ab)
end
p acc                                                   # => 4