典型タグ

difference constraints・不等式系の最短路化

差の上界 x_v-x_u≤c を有向辺 u→v の重みcへ写し、Bellman–Ford等の緩和と負閉路から可解性・極値・具体解を求める。

この典型を扱う単元: difference constraints・不等式系の最短路化

検索別名: constraint graph、difference constraints、差の不等式、差分制約

未知問からこの典型を見つける手掛かり

扱う対象
  • constraint graph
  • variables
  • x_v-x_u<=c
使う手掛かり
  • prefix sum inequality
  • 差の上界または下界
  • 整数列の区間個数制約
保つ不変量
  • edge relaxation preserves every upper bound
  • negative cycle iff infeasible
求めるもの
  • 制約を満たす列の構成
  • 可解性判定
  • 変数の極値
適用しない条件
  • online union/query
  • 等式だけのpotential伝播
分類・前提・学習成果

分類と直接の前提

概念上の親: グラフモデルと構造

関連する典型

  • 最短路モデル: 各不等式 x_v-x_u<=c を有向辺 u->v の緩和条件へ写し、可解性・極値を最短路または負閉路判定へ帰着する。

学習成果と学習単位

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。