AtCoder Regular Contest 106 B – Values を解いた記録

問題の概要

\(N\)頂点\(M\)辺の単純無向グラフが与えられる.\(i\)番目の辺は頂点\(c_{i}\)と頂点\(d_{i}\)を結ぶ.

はじめ,頂点\(i\)には荷物が\(a_{i}\)個ある.次の操作を0回以上行い,頂点\(i\)には荷物が\(b_{i}\)個ある状態にしたい.
それが可能な場合は”Yes”を,不可能な場合は”No”を出力せよ.

  • ある辺により結ばれている頂点\(x, y\)の間で,荷物を1つ移動する.

問題へのリンク

制約

  • \(1 \leq N \leq 2 \times 10^{5}\)
  • \(0 \leq M \leq 2 \times 10^{5}\)
  • \(-10^{9} \leq a_{i}, b_{i} \leq 10^{9} \)
  • \(1 \leq c_{i}, d_{i} \leq N \)
  • 与えられるグラフは単純グラフ
  • 入力はすべて整数

解法

グラフの各連結成分について,各頂点にある荷物の数の総和は操作前と操作後で変化しません.

よって,やるべきことは

  • 連結成分を判定する
  • 各連結成分について,操作前の各頂点にある荷物の数の総和と操作後の各頂点にある荷物の数の総和を計算する
  • 操作前の各頂点にある荷物の数の総和と操作後の各頂点にある荷物の数の総和が異なるような連結成分が1つでもあれば”No”を,1つもなければ”Yes”を出力する

となります.

連結成分の判定は,UnionFindを使うのが楽でしょう.UnionFindで各頂点の親となる頂点(各連結成分の代表となる頂点)もわかるので,総和の計算も楽になります.

各連結成分について各頂点にある荷物の数の総和を計算するときは,以下のようにすると楽だと思います.

  1. 総和を計算するための配列\(beforesum, aftersum\)を用意する
  2. 各\(i\)について次の操作を行う
    • 頂点\(i\)の親となる頂点の番号\(parent(i)\)を見つける(UnionFindを使っている場合は一発でわかる)
    • \(beforesum[parent(i)]\)に\(a_{i}\)を,\(aftersum[parent(i)]\)に\(b_{i}\)を足す
  3. \(beforesum[i] \neq aftersum[i]\)となるような\(i\)があるかを確認

実装例


UnionFindは経路圧縮のみの簡単なものですが,これでもちゃんとACできます.

感想

UnionFindは自前ライブラリを用意していましたが,使いたいときにすぐ使える状態にしていないと自前ライブラリの意味がありません.2完早解きコンテストを戦うならなおさらです.
今回も早解き失敗で緑パフォとなったので色変は次回以降へ持ち越しです….