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文章

习题