Skip to content

差分约束 Differential Constraints

算法

差分约束系统 是一种特殊的 \(n\) 元一次不等式组，都是\(x_i-x_j\leq c_k\)的形式。问是否存在一组解，满足所有的差分约束。

差分约束系统中的每个约束条件 \(x_i-x_j\leq c_k\) 都可以变形成 \(x_i\leq x_j+c_k\)，这与单源最短路中的三角形不等式 \(dist[y]\leq dist[x]+z\) 非常相似。因此，我们可以把每个变量 \(x_i\) 看做图中的一个结点，对于每个约束条件 \(x_i-x_j\leq c_k\)，从结点 \(j\) 向结点 \(i\) 连一条长度为 \(c_k\) 的有向边。

设 \(dist[0]=0\) 并向每一个点连一条权重为 \(0\) 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，\(x_i=dist[i]\) 为该差分约束系统的一组解。

一般使用 Bellman-Ford 或队列优化的 Bellman-Ford（俗称 SPFA，在某些随机图跑得很快）判断图中是否存在负环，最坏时间复杂度为 \(O(nm)\)。

完整的说明见OI-Wiki文章

习题