P1993 小 K 的农场 题解

严肃学习差分约束。

具体而言，对若干个不等关系可以考虑建图。假设不等关系形如 $x_a-x_b\le c$，那么从 $b$ 向 $a$ 连一条边权为 $c$ 的单向边。

同理，对于 $x_a-x_b\ge c$ 的不等关系，考虑对不等式两边同时乘 $-1$ 然后不等式变号，得到 $x_b-x_a\le -c$，从 $a$ 向 $b$ 连一条边权为 $-c$ 的单向边。

而对于 $x_a=x_b$ 这样的关系，容易证明其和 $x_a\ge x_b,x_a\le x_b$ 两个不等式同时满足是完全等价的，因此按照上面的两个方式分别建两条边即可。

从超级源点 $S$ 向所有点 $i=1\ldots n$ 都连一条边权为 $0$ 的有向边，从 $S$ 开始跑最短路即可。

而判断其无解当且仅当该图存在从 $S$ 出发的负环，而若有解，其一组合法解即为最短路得到的 dis 数组。

判断负环可以使用 spfa 或者 bellman-ford 算法，时间复杂度均为 $O(nm)$。