差分约束

约 208 个字 预计阅读时间 1 分钟

多元一次不等式，$x_i$ 未知，$y_i$ 已知

$$\begin{cases}x_{c_1}-c_{c_1'}\le y_1\\ x_{c_2}-c_{c_2'}\le y_2\\ ...\\x_{c_n}-c_{c_n'}\le y_n\end{cases}$$

对于每个约束，从 $c_i'$ 向 $c_i$ 连边权 $y_i$ 的有向边，0点作为超级源点向所有点连边权0的有向边，用bellman-ford跑单源最短路，如果存在负环则无解。

dis[i]表示 $x_i$ 的一组可行解，所有 $x_i$ 加上同一个数，答案仍可行

dis[0]=w，可以得到 $x_i\le w$ 的最大解（每个变量取到能取到的最大值），最小解求最长路即可，把比较符号逆转，距离初始化为-INF。

实际问题通过移项，加减1，两个小于等于实现等于，来转换。