差分约束

简介

差分约束系统（System of Difference Constraints），是求解关于一组变数的特殊不等式组之方法。

如果一个系统由 nn 个变量和 mm 个约束条件组成，其中每个约束条件形如
xj−xi≤bk(i,j∈[1,n],k∈[1,m])x_j - x_i \leq b_k (i,j \in [1, n], k \in [1, m])，则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
如果xi−xj≤dx_i - x_j \leq d。

那么从jj向ii连接一条长度为dd的边。

这样求最短路，一定满足xi≤xj+dx_i \leq x_j + d。

判断有无解

判断图有没有负环即可，如果发现了负环，说明找到了矛盾。

值得注意的是这个负环问题是全局有没有负环，所以看起来需要所有点同时入队。

求出一组解

有的时候不仅要判断一组解，而需要求出一组解。

参考题目

Luogu P1250

Luogu P1993

  1. 差分约束
    1. 简介
    2. 判断有无解
    3. 求出一组解
    4. 参考题目
≡