ポテンシャル付きDSU：差を保つ

「重みの差が d」という制約で頂点を結びます。代表への差を保存すると、既知の関係の矛盾を検出できます。

言語：Python / 計算量：重み付きDSUで償却 O(α(N)) / 操作

前提：Union-Findで連結を管理

考え方

1. weight[x] を x から親へのポテンシャル差と定義。
2. 根までの和が x と根の差になります。
3. 根を接続するときに制約が成立するよう差を設定します。

具体例

P1-P0=2、P2-P1=3 なら P2-P0=5。ここに P2-P0=4 が来たら矛盾します。

実装

# 少数の固定制約をポテンシャルで検証
p=[0,2,5]
constraints=[(0,1,2),(1,2,3),(0,2,4)]
print(all(p[v]-p[u]==d for u,v,d in constraints))

注意する条件

差の向きを最初に固定します。根の大小で併合方向を反転するときは差の符号も反転します。

確認問題

P1-P0=2、P2-P1=3 のとき P2-P0 は？

実装課題

連結な差分制約グラフが与えられる。各行 u v d は P_v-P_u=d。矛盾がなければ Yes。N,M≤200000。静的なので探索で解く。

入力:
3 3
0 1 2
1 2 3
0 2 4
出力:
No

n,m=map(int,input().split());g=[[] for _ in range(n)]
for _ in range(m):
    u,v,d=map(int,input().split());g[u].append((v,d));g[v].append((u,-d))
p=[None]*n;p[0]=0;stack=[0];ok=True
while stack:
    v=stack.pop()
    for u,d in g[v]:
        if p[u] is None:p[u]=p[v]+d;stack.append(u)
        elif p[u]!=p[v]+d:ok=False
print("Yes" if ok else "No")

読了の記録・下書き・メモへ