算法简介
差分约束算法是用于求解不等式组的解的一种算法。具体描述如下：
给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如：
$$ \begin{cases} x_{c_1}-x_{c’_1}\leq y_1 \\x_{c_2}-x_{c’_2} \leq y_2 \\ \cdots\\ x_{c_m} – x_{c’_m}\leq y_m\end{cases}$$
的不等式组，求任意一组满足这个不等式组的解。
问题转化
根据基础的数学知识，可以把上述的任意一个不等式 $x_i-x_j \le c$ 转化为如下形式：
$$x_i \le x_j + c$$
这可太简单了，小学生都会做这样的变形（好像不等式初中才会学）。
但是转化为这种形式后，你会发现它与最短路算法中的三角不等式特别的相似（三角不等式也就是最短路算法中的松弛操作）
$$dis_i<dis_j+v$$
于是，使用最短路算法求解该问题的想法油然而生。
把每个变量 $x_i$ 都看作是一个顶点，并设置一个超级源点 $x_0$ ，把超级源点向所有的顶点都连接一条有向边，边权为 $0$ ，把不等式 $x_i \le x_j + c$ 转化到图上，表示为顶点 $x_j$ 向 $x_i$ 连接一条有向边，边权为 $c$ ，这样一来，所有的不等式都表示在一张图上，从超级源点开始，向每一条边跑一次最短路，得到超级源点到每个点的最短路长度 $dis_i$ ， $dis_i$ 就是 $x_i$ 的一个值。
在不等式组有解得情况下，可以求出所有点的最短路。如果没有解，说明图中出现了负环，只要图中出现了负环，就可以说这个不等式组没有解。
本题可以使用SPFA算法，在寻找最短路的同时找到负环。
原理解释
为什么上面的做法一定是对的呢？
假设说我们已经求出了超级源点到 $x_i$ 的最短路是 $dis_i$ ，我们要根据 $dis_i$ 和不等式 $x_j \le x_i +c$ 确定 $x_j$ 的范围，经过表示这个不等式的边权为 $c$ 的边，我们就可以得到当前状态下 $x_j$ 的最大值 $dis_j$ ，寻找这个最大值是为了让被 $x_j$ 约束的未知量有更大的取值范围，而由于 $x_j$ 这个未知量还会被其他的不等式约束，所以我们要去找一条最短路，也就是满足所有约束要求的最大值。只要原不等式组有解，我们就一定能找出这组解，因为通过上述原理找出的未知量都是最优的。
所有最短路跑完之后，我们就可以得到不等式组的其中一个解了。如果没有解，表现在图上即是负环，因为我始终找不到满足上述不等式的未知量的值。
代码
Fast命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。
#include<bits/stdc++.h>
using namespace std;
namespace Fast {...}
using namespace Fast;
int n, m, xx, yy, c, inp[M], dis[M], minn;
bool vis[M];
struct Node {
int nxt, to, v;
} e[M];
int g[M], nxt;
queue<int>q;
void add(int x, int y, int v) {
e[++nxt].to = y;
e[nxt].nxt = g[x];
e[nxt].v = v;
g[x] = nxt;
return;
}
int main() {
read(n, m);
for (int i = 1; i <= m; i++) {
read(xx, yy, c);
add(yy, xx, c);
}
for (int i = 1; i <= n; i++) {
dis[i] = inf;
add(0, i, 0);
}
q.push(0);
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int k = g[x]; k; k = e[k].nxt) {
int y = e[k].to, v = e[k].v;
if (dis[x] + v < dis[y]) {
dis[y] = dis[x] + v;
inp[y] = inp[x] + 1;
if (inp[y] >= n) {
prints("NO");
return 0;
}
if (vis[y])
continue;
q.push(y);
vis[y] = 1;
}
}
}
for (int i = 1; i <= n; i++) {
print(dis[i]);
space;
}
return 0;
}
