差分约束

定义

差分约束系统 是一种特殊的 $n$ 元一次不等式组，它包含 $n$ 个变量以及 $m$ 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 $x_i-x_j\leq c_k$，并且 $c_k$ 为常实数。

解决问题

求出该系统的（任意）一组解，或判断无解。

变形

每个约束条件 $x_i-x_j\leq c_k$ 都可以变形成 $x_i\leq x_j+c_k$，这与单源最短路中的三角形不等式 $dist[y]\leq dist[x]+w$ 非常相似。

建模

因此，我们可以把每个变量 $x_i$ 看做图中的一个结点，对于每个约束条件:

$$x_i-x_j \leq c_k \Leftrightarrow x_i \le x_j+c_k$$

从结点 $j$ 向结点 $i$ 连一条长度为 $c_k$ 的有向边。

这样跑一遍最短路得出的 dist[] 数组就是满足当前约束条件的一组解。

可是最短路总要有个源点，注意到建立的图不一定是连通图，所以使用一个超级源点，向每个节点连一条边权为 $0$ 的边。

为什么边权为零？
假设超级源点为 $0$ 节点，根据最短路的定义 $dist[0]$，因此对于每个节点连一条边权为 $0$ 的边就相当于添加了 $n$ 个条件 $x_i \le x_0 + 0 = x_0 = 0$。

注意到，如果 $\{a_1,a_2,\dots,a_n\}$ 是该差分约束系统的一组解，那么对于任意的常数 $d$，$\{a_1+d,a_2+d,\dots,a_n+d\}$ 显然也是该差分约束系统的一组解，因为这样做差后 $d$ 刚好被消掉，也就是说，差分约束得到的解是可以在数轴上任意平移的。

因为可行解可以任意平移，这些约束条件使得我们找到的是最大值为 $0$ 的一组解，并不影响解的正确性。由此可知，边权为 $0$ 只是一种被人们广泛接受的习惯，实际上它可以为 任意实数。赋值成 $0$ 可以帮助人们理解并且避免解超出范围。

Code

Problem : P5960 【模板】差分约束

Application

P1260 工程规划

Analysis

相较于模版，本题额外要求：

对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说，$T _1,T_2,\dots,T_n$中至少有一个为 0。

这就用到了差分约束中解的平移性，我们可以设，$M = \min_{1 \le i \le n}{T_i}$，这样将每个解同时减去 $M$，就会得到一组合法的解（最小值等于0）

Code