这是本文档旧的修订版!
差分约束系统是关于 $n$ 个未知量的 $m$ 个形如 $x_i-x_j\le k$ 不等式组。一般来求解的存在性问题、最优值问题以及方程组的解。
考虑松弛过后的最短路$dis$数组,对任意一条长度为$k$从$x$到$y$的有向边,满足$ dis_y \le dis_x + k $,移项得到$ dis_y - dis_x \le k $,这与开头提到的$ x_i - x_j\le k $神似。因此我们将每个变量看成一个点,对每个不等式$ x_i - x_j\le k $连一条从$x_j$到$x_i$的长度为$k$的有向边即可,若图存在负环,意味着通过不等式相加可以得到自己小于自己,那么显然是无解的,否则一定有解,因此判负环即可。