定义
差分约束系统 是一种特殊的 \(n\) 元一次不等式组，它包含 \(n\) 个变量 \(x_1,x_2,...x_n\) 以及 \(m\) 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 \(x_i-x_j\le c_k\)，其中 \(1\le i,j\le n,i\not=j,1\le k\le m\) 并且 \(c_k\) 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 \(x_1=a_1,x_2=a_2,...x_n=a_n\)，使得所有的约束条件得到满足，否则判断出无解。
简单来讲就是给定几条不等式，求出某个可行解。
应用
将图建起来，跑最短路/最长路。
建图基本方法
以 P5960 【模板】差分约束 为例。
已知式子 \(x_1-x_2\le c\) 。
那么就可以将式子转化为 \(x_1\le c+x_2\) 。
那么假设我们同时存在多条对于 \(x_1\) 的限制，由于我们肯定希望 \(x_1\) 尽量大，这样子这个点作为 \(x_2\) 时的 \(x_1\) 的范围才会尽量大，得到最大的情况即可。
那么我们可以将建图，由 \(x_2\) 指向 \(x_1\)， 边权为 \(c\)，跑最短路，这样就能够在符合条件时得到一组解。
例题按照上述方法即可。
不同情况的转化
如果式子不仅有上述式子，还存在 \(x_1-x_2\ge c\)又该怎么处理？
直接两边取反，因为两边取反后大小于符号也会改变，那么再转化为 \(x_2\le -c+x_1\)。
再次跑最短路即可。
同理我们也可以更改建边方式跑最长路。
有解无解的判断
如果你跑最短路出现负环或者最长路出现正环，那么就是无解的，直接spfa或者其它找环方式即可，但是需要注意开一个超级源点。
超级源点
连向所有节点，可以使无相关的两个图都跑到。
某两个点间是否有限制
从其中一个点开始跑，如果另一个点没有影响，那么就无限制，即两者相互独立。
跑法
通常是 spfa，但是spfa经常spfa，如果spfa完全不怕spfa，那么直接用就可以了
但是有时会超时，那么看看有没有负边权，没有或者可以转化为没有就用dij
如果看有没有解，而且边权比较单一，那么也能来一手拓扑排序
如果要全源，考虑floyed或者多次dij
乘法差分约束
普通方法直接开始乘除
但是还有一种log相加的方法