考察
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.
出典