本文主要是介绍【图论】差分约束，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

差分约束

1. 求不等式组的可行解

对于以上不等式，差分约束可以得到一组可行解。

在最短路中，求完最短路后，对于每个从j->i可以看成一个不等式\(x_i \leq x_j + c\)
说通俗点就是给我们一个图，我们可以把每条边看成一个不等式，我们在这个图上求每个点到源点的最短距离，求完之后，每个边的不等式必然满足\(x_i \leq x_j + c\)
也就是说，任何一个最短路问题都可以变成一个差分约束问题。
反过来也一样，对于一个不等式组中的任何一个不等式来说，我们都可以把它看成是一个从j走到i，长度是\(c_k\)的一条边，然后在图上随便选择一个起点，求一下每个点到起点的最短距离，求完之后，也必然满足\(x_i \leq x_j + c_k\)。因此，每个差分约束问题都可以转化成图论的单源最短路问题。

因此，当我们想求某一组可行解的时候，我们可以把不等式组中的每一个不等式转化成一条边，然后在图上求某一个点的单源最短路径，求完之后得到的结果必然满足不等式组中的限制条件，所以我们也就可以得到一个可行解。

但是，我们往往不能任取一个源点，源点需要满足一定的条件。
源点需要满足的条件：从源点出发，一定可以走到所有的边。
因为只有从源点出发可以到达的边才满足不等式\(x_i \leq x_j + c\)。

这样的话，对于每一个不等式组，我们一般可以分成两步来做:
1.把每一个不等式\(x_i \leq x_j + c_k\) 变成从j到i，长度是\(c_k\)的一条边。
2.找到一个可以走到所有边的源点（一般为虚拟（超级）源点）。
3.从这个源点求一遍单源最短路。

当然，这里也有个问题，并不是所有的图都存在最短路，如果存在负环怎么办呢？
如果存在负环，还原到不等式中的结果就是会推出\(x_i \leq x_i +c\)，因为负环，所以\(c\)是一个负数，一个数是不可能小于其本身加一个负数的，即出现\(x_i < x_i\)，一个数小于其自己，这就出现了矛盾。

所以如果图中存在负环，则其转化成的不等式组一定存在\(x_i < x_i\)的矛盾，
反过来，不等式组中如果存在\(x_i < x_i\)的矛盾，则其转化成的图中一定存在负环。
所以不等式组无解等价于图存在负环。
即：1.如果存在负环，则原不等式组一定无解。
2.如果不存在负环，则一定可以找到原不等式组的一组可行解。跑完单源最短路算法之后，dist[i]就是原不等式组的一个可行解。
在最短路问题中，无解等价于图存在负环。
一图总结上文：

另外，上面是用最短路求可行解，最长路当然也是可以求可行解的。
观察可知：如果把不等式组的问题变成最短路的话，j到i有一条长度为\(c_k\)可以变成\(x_i \leq x_j + c_k\)，求完最短路后满足\(dist[i] \leq dist[j] + c_k\)

类比到最长路，求完最长路后，满足\(dist[i] \geq dist[j] + c_k\)

相当于是i到j连了一条长度为\(-c_k\)的边。

相应的，在最长路问题中，无解就等价于图存在正环。

当然，在求可行解的时候，用最短路或者最长路都是可以的。
用最短路求解:
将所有不等式转化成\(x_i \leq x_j + c_k\)的形式，然后从j到i连一条长度为\(c_k\)的边。
用最长路求解：
将所有不等式转化成\(x_j \geq x_i - c_k\)的形式，然后从i到j连一条长度为\(-c_k\)的边。
如果想连正边，也可以写成\(x_i \geq x_j + c_k\)，然后从j到i连一条长度为\(c_k\)的边。

之前刚学的时候还有一个疑问：
单源最短路不是：\(dist[j]>dist [i]+c\);则，\(dist[j]=dist[i] + c;\)吗？怎么理解 \(dist[y]<=dixt[x]+z\)?
答：正因为满足\(dist[j]>dist [i]+c\)，所以跑完单源最短路算法后才会有：\(dist[y]<=dixt[x]+z\)，因为不满足\(dist[y]<=dixt[x]+z\)就会更新它，让他满足\(dist[y]<=dixt[x]+z\)为止。

2. 如何求最大值或者最小值（实际题目中问的问题）

之前谈到了求可行解，通过把一个不等式组中的不等式转化成图中的边，找一个可以到达所有点的源点跑单源最短路算法，如果图中存在负环，则原不等式组无解，如果图中没有负环，则dist[i]即就是不等式组的一组可行解。
现在的问题是，我们如何求一个最小的可行解或者最大的可行解呢？

如果要求最小值或最大值的话，则不等式组中必然有一个不等式长成这样：\(x_i \geq c\)或者\(x_i \leq c\)，\(c\)为常数。可以想一下，如果不等式组中的所有不等式都是变量形式的不等关系，那么整个不等式组都是一种相对的关系，但是如果不等式组内的某个不等式中的某一边全部为常数，则整个不等式组的状态就由一种不确定的相对关系转变到了确定的绝对关系，因为有了常数，经过条件的恒等变换，不等式组就一定大于等于或小于等于一个全部由常数构成的式子，那么这个全部由常数构成的式子的值就是不等式组的最值。

实际上也确实如此，算法题目中如果要让我们求最值，也一定会给出一个“\(x_i \geq c\)或者\(x_i \leq c\)，\(c\)为常数”的式子，这样我们才能求出最值，不然都是相对关系。

PS：最短路给出的不等式为\(x_i \leq c\)
最长路给出的不等式为\(x_i \geq c\)

那么现在的问题就变成了：如何把“\(x_i \geq c\)或者\(x_i \leq c\)，\(c\)为常数”的式子转化成图中的一条边呢？
方法：
我们以最短路的不等式\(x_i \leq c\)为例进行说明：
建立一个虚拟（又称超级）源点，通常为0号点，对于\(x_i \leq c\)，可以转化成\(x_i \leq x_0 + c\)
，其中\(x_0\)是0，所以这个等式就可以转化为从0到i有一条长度为 \(c\) 的边，问题解决。

另外，我们这里求的最大值最小值是指不等式组中每个变量的最大值最小值。
如\(x_1\)的最值，\(x_2\)的最值，...，以此类推。

比如说我们想求一下\(x_i\)的最大值，那么我们可以枚举一下所有\(x_i\)的链式关系，即找到所有与\(x_i\)相关的不等式，然后经过条件变换、放缩，最后一定可以转化成一个不等式，这个不等式的右边一定没有变量，只有常数。（否则的话都是相对关系，求不出来上限）

所以我们想求\(x_i\)的上界，其实就是看一下所有\(x_i\)构成的不等式链，求一下每个链的上界，然后在所有的上界中找出最小的那个上界，就是答案。

举个例子：比如说我们求出了
\(x_i \leq 5\)
\(x_i \leq 2\)
\(x_i \leq 3\)
那么\(x_i\)的最值应该取多少？ 答案是2
因为只有\(x_i \leq 2\)才能满足所有的条件，并不是看到5最大所以5是最大值，5是最大值它满足不了所有条件。

而上述的每一个不等式链都可以转化为图论中的一条路径，即每条不等式链都是从0号点出发，走到i号点的一条路径。
求每个不等式链的上界就相当于求图论中每一条路径的最短路，然后在求出的所有最短路中找出最小的那个最短路，这就是我们要找的答案。
结合上面的例子，此时在所有最短路中找出的值最小的最短路就是在可以满足所有约束条件的情况下的最小上界。

同理，比如说我们求出了
\(x_i \geq 5\)
\(x_i \geq 2\)
\(x_i \geq 3\)
那么满足条件的\(x_i\)应该取的值就是5
因为只有\(x_i \geq 5\)可以满足所有条件。
这里找的就是最大的下界。

综上：求最小值其实求的是在满足所有约束条件下最小的那个上界(即值最小的最短路)。
求最大值其实求的是在满足所有约束条件下最大的那个下界(即值最大的最长路)。

这篇关于【图论】差分约束的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！