ABC 280 F — Pay or Receive

考察

roadを往復するとscore変化が符号反転するため、連結成分内でrootから各頂点へのpotentialが一意なら任意pathのscore差も一意になる。同じ頂点へ異なるscoreで到達できるなら差を持つclosed walkがあり、正になる向きで何度も回ってscoreを無限に増やせる。consistent componentでは任意のx→y walk scoreはpot[y]-pot[x]で、closed walk scoreは全て0になる。不整合edgeが1本でもあるcomponentでは非零closed walkを両方向のうち有利な向きに反復でき、同componentの任意x,y queryがinfになる。

採用する候補: 各componentをDFSし、edge A→Bでpot[B]=pot[A]+Cを割り当て、既割当てとの矛盾があればcomponentをunboundedと印付ける。

連結性・有限時のscore差・非零cycleの有無を一度の前処理で得て、queryを定数時間で分類できる。

棄却する候補: 各queryごとに最大score pathをBellman-Ford等で探索する。

Q,N,M≤10^5で繰返し最短路は重く、undirected符号edgeのpotential構造を活かしていない。

未訪問vertexごとにcomponent idとpot=0を置き、(u,v,+c)をDFS緩和する。pot[v]≠pot[u]+cを見つけたcomponentをbadにする。queryはcomponent不同ならnan、badならinf、それ以外はpot[y]-pot[x]。

典型の発動条件

potential付きgraph

発動条件: edgeが頂点値の差を指定し、path和の一意性や矛盾を判定したいとき。

rootからpotentialを割り当て、各edgeが差分式を満たすか検査する。

非零cycleによるunbounded判定

発動条件: cycleを繰り返せるwalk最適化で、cycle利得が0でないとき。

符号反転可能なclosed walkを有利な向きに反復してinfとする。

問題固有の要素

各roadの逆向きscoreが正確に−Cなので、cycle矛盾は単なる有限の別解ではなく、向きを選べる無限利得へ直結する。

別の問題へ持ち帰る視点: 可逆edgeの加法scoreでは、path差の不整合がreversible profitable cycleになるかを見る。

正当性

矛盾がなければ全辺scoreがpotential差となり任意pathのscoreは終点差へtelescopingする。矛盾があれば非零closed walkがあり、逆向きで符号を選んで正scoreを無限反復できる。同成分からそこへ往復可能なのでinf。別成分はpathなし。

実装上の注意

  • A→Bで+C、B→Aで−Cを隣接listへ保存し、potentialの符号をquery式まで統一する。
  • self-loop C>0やparallel edgeの不一致もbad検出対象で、potentialと答えは64 bitにする。

復習の核

  • 同じ2頂点を異なるCのparallel roadで結ぶ例から非零closed walkを作り、なぜcomponent全queryがinfになるか説明する。

計算量と制約

時間

N 頂点、M road、Q質問。potentialDFS O(N+M)、各質問 O(1)。

空間

符号付き隣接、component、potential O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2\leq N \leq 10^5; 0\leq M \leq 10^5; 1\leq Q \leq 10^5; 1\leq A_i,B_i,X_i,Y_i \leq N; 0\leq C_i \leq 10^9; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Pay or Receive の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 静的graph等式制約のpotential伝播

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 静的graph等式制約のpotential伝播

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 静的graph等式制約のpotential伝播

      • 辺等式をDFS/BFSでroot-relative potentialへ伝播し、cycle矛盾を検出して各連結成分の全解を自由offset一つで表現・復元できる。

      先に読む単元:

      • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題