potential・weighted DSU
親へのpotential差を保ち、同一成分内の差制約と矛盾をmerge・queryできる。
この典型を扱う単元: potential・weighted DSU
検索別名: potential DSU、weighted Union-Find、重み付きUnion-Find
未知問からこの典型を見つける手掛かり
- 扱う対象
- potential
- 差制約
- 成分
- 使う手掛かり
- offset
- 相対差
- 矛盾
- 保つ不変量
- cycle和
- rootへのpotential
- 求めるもの
- 差query
- 整合性判定
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- DSUによる連結成分管理・縮約: 通常のDSUにrootまでの差分potentialを持たせ、merge時にoffsetを調整する。
- 静的graph等式制約のpotential伝播: 固定graph上で等式を一括伝播する方法と、辺追加に追随して差分potentialを保つ方法を区別する。
学習成果と学習単位
DSUの親辺にpotential差を持たせ、経路圧縮時の差の累積と根の併合方向に応じた符号を導出し、オンラインの差制約追加と頂点間差・矛盾のqueryを処理できる。
potential・weighted DSUで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。