差分约束是用来解多个不等式中一个什么玩意儿的MAX或MIN 或者是这么一大堆式子有没有解

v - u > x     巴拉巴拉好多这样的式子

看一下最短路是如何运作的 

在一张已经维护好的图上 有dis[v]<=dis[u]+way[u][v];

把上面的式子Duang Duang Duang一顿转换后得到 

u - v < -x

u < v + (- x)

实现到图上就是 addedge( u, v , -x)  从u到v连一条边 长度为dis 表示从v 至少比 u 大 -x;

（其实这里理解了的话应该会感觉很这种做法很聪明）

那怎么判这些式子成不成立？

在原式之中可能会发现一些特别蠢的式子像 x>y   y>z   z>x 这很明显是无解的

建好图之后表现在图上就是 有个正环或是负环 （0环没事 可以自己理解一下

看到这里应该可以了解到 如果你建的不是一张DAG 那它无解（环为0时除外

代码实现就是跑个spfa判个环完事

bool vis[N];bool spfa(int u){    vis[u]=1;    for(int i=head[u];i;i=edge[i].nxt){        if(dis[edge[i].to]

有个板子叫 （超链接写好了哦）

 

差分约束还可以解决一些 像什么在确定了一个值的基础上求另一个点的MIN / MAX;

板子  （超链接点击即可） 当然了这个题贪心也能过 但是用来差分入门也很好