差分约束 Differential Constraints

差分约束 Differential Constraints

算法

差分约束系统 是一种特殊的 nn 元一次不等式组，都是xi−xj≤ckx_i-x_j\leq c_k的形式。问是否存在一组解，满足所有的差分约束。

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

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

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

完整的说明见OI-Wiki文章

习题
P1993小K的农场普及+/提高解答
P3275糖果提高+/省选-
P4926倍杀测量者省选/NOI-解答
POJ1364King解答
P8098USACO GoldTests for Haybales2022省选/NOI-解答
算法标签Tree construction, differential constraints