

差分约束

Copyright

本页面贡献者：DcmTruman。 本页面内容遵循 MIT 协议，转载请附上原文出处链接和本声明。

假设我们现在有这样一个问题

• 若干变量
• 变量差来约束关系 $x_{1}-x_{2} > 1$ $x_{2}-x_{3} > 2$ $...$
• 求解(任意解、一组解、最大最小解）

• 怎么做？

• 差分约束系统 是一种特殊的 $n$ 元一次不等式组，它包含 $n$ 个变量 $x_1,x_2,...,x_n$ 以及 $m$ 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 $x_i-x_j\leq c_k$ ，其中 $c_k$ 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 $x_1=a_1,x_2=a_2,...,x_n=a_n$ ，使得所有的约束条件得到满足，否则判断出无解。

还记得最短路吗？

差分约束系统中的每个约束条件 $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$ 并向每一个点连一条边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则， $x_i=dist[i]$ 为该差分约束系统的一组解。

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

例题 luogu P1993 小 K 的农场

题目大意：求解差分约束系统，有 $m$ 条约束条件，每条都为形如 $x_a-x_b\geq c_k$ ， $x_a-x_b\leq c_k$ 或 $x_a=x_b$ 的形式，判断该差分约束系统有没有解。

题意	转化	连边
$x_a - x_b \geq c$	$x_b - x_a \leq -c$	add(a, b, -c);
$x_a - x_b < c$	$x_a - x_b \leq c-1$	add(b, a, c-1);
$x_a = x_b$	$x_a - x_b \leq 0, \space x_b - x_a \leq 0$	add(b, a, 0), add(a, b, 0);

最长边版本

也可以改成 $\ge$,不过要求最长路，初始值-INF

题意	转化	连边
$x_a - x_b \leq c$	$x_b - x_a \geq -c$	add(a, b, -c);
$x_a - x_b > c$	$x_a - x_b \geq c+1$	add(b, a, c+1);
$x_a = x_b$	$x_a - x_b \leq 0, \space x_b - x_a \leq 0$	add(b, a, 0), add(a, b, 0);

有一条线段，1到n，n个位置，你有m个棋子，现在你可以在每个位置放一些棋子，给你q个区间条件$a,b,c$，表示$[a,b]$区间最少要有c个棋子，问你至少要用多少个棋子

• $d_{i}$表示前i个位置的棋子个数，对于条件，则是$d_{b}-d_{a-1} \ge c$
• $d_{i+1} - d_{i} \ge 0$
• $d_{n} - d_{0} \le m$
• 二分+差分约束spfa判断是否有解