静的graph等式制約のpotential伝播
可逆な加法・XOR演算で x_v=x_u⊙w と書ける辺等式をDFS/BFSで伝播し、cycle整合性を検査して各連結成分の解をroot offset一つで表す。
この典型を扱う単元: 静的graph等式制約のpotential伝播
検索別名: XOR potential graph、graph potential propagation、グラフpotential、静的差分等式制約
未知問からこの典型を見つける手掛かり
- 扱う対象
- root-relative potential
- 加法群またはXOR群
- 辺等式制約
- 使う手掛かり
- x_v=x_u⊙w
- 全制約が静的
- 成分ごとの自由offset
- 保つ不変量
- component-wide offset
- cycle consistency
- path potential
- 求めるもの
- 可解性判定
- 成分offsetの最適化
- 相対値復元
- 適用しない条件
- negative cycle
- online union/query
- 不等式の上界
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- potential・weighted DSU: 固定graph上で等式を一括伝播する方法と、辺追加に追随して差分potentialを保つ方法を区別する。
学習成果と学習単位
辺等式をDFS/BFSでroot-relative potentialへ伝播し、cycle矛盾を検出して各連結成分の全解を自由offset一つで表現・復元できる。
静的graph等式制約のpotential伝播で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。