一：差分约束的定义

差分约束系统（system of difference constraints），是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。

通俗一点地说，差分约束系统就是一些不等式的组，而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。

比如：

二：差分约束的求解 

分约束系统可以转化为图论来解决，对应于上面的不等式组，如果要求出x3-x0的最大值的话，叠加不等式可以推导出x3-x0<=7,最大值即为7，我们可以通过建立一个图，包含6个顶点，对每个xj-xi<=bk，建立一条i到j的有向边，权值为bk。通过求出这个图的x0到x3的最短路可以知道也为7，这是巧合吗？并不是。

之所以差分约束系统可以通过图论的最短路来解，是因为xj-xi<=bk，会发现它类似最短路中的三角不等式d[v] <=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。而求取最大值的过程类似于最短路算法中的松弛过程。

三角不等式：（在此引用大牛的博客）

B - A <= c     (1)

C - B <= a     (2)

C - A <= b     (3)

 如果要求C-A的最大值，可以知道max（C-A）= min(b,a+c),而这正对应了下图中C到A的最短路。 

因此，对三角不等式加以推广，变量n个，不等式m个，要求xn-x1的最大值，便就是求取建图后的最短路。

同样地，如果要求取差分约束系统中xn-x1的最小值，便是求取建图后的最长路。最长路可以通过spfa求出来，只需要改下松弛的方向即可，即if(d[v] < d[u] + dist(u,v)) d[v] = d[u] + dist(u,v)。当然我们可以把图中所有的边权取负，求取最短路，两者是等价的。
 

最后一点，建图后不一定存在最短路/最长路，因为可能存在无限减小/增大的负环/正环，题目一般会对应于不同的输出。判断差分约束系统是否存在解一般判环即可。

三：差分约束的应用

差分约束系统的应用很广，都会有一定的背景，我们只需要根据题意构造出差分约束系统，然后再根据题目的要求求解就行了。

一般题目会有三种情况：(1)、求取最短路 (2)、求取最长路 (3)、判断差分约束系统的解是否存在

当然这三种也可能会相互结合。

差分约束系统的解法如下：

1、  根据条件把题意通过变量组表达出来得到不等式组，注意要发掘出隐含的不等式，比如说前后两个变量之间隐含的不等式关系。

2、  进行建图：

首先根据题目的要求进行不等式组的标准化。

(1)、如果要求取最小值，那么求出最长路，那么将不等式全部化成xi – xj >= k的形式，这样建立j->i的边，权值为k的边，如果不等式组中有xi – xj > k，因为一般题目都是对整形变量的约束，化为xi – xj >= k+1即可，如果xi – xj = k呢，那么可以变为如下两个：xi – xj >= k, xi – xj <= k,进一步变为xj – xi >= -k，建立两条边即可。

(2)、如果求取的是最大值，那么求取最短路，将不等式全部化成xi – xj <= k的形式, 这样建立j->i的边，权值为k的边，如果像上面的两种情况，那么同样地标准化就行了。

(3)、如果要判断差分约束系统是否存在解，一般都是判断环，选择求最短路或者最长路求解都行，只是不等式标准化时候不同，判环地话，用spfa即可，n个点中如果同一个点入队超过n次，那么即存在环。

值得注意的一点是：建立的图可能不联通，我们只需要加入一个超级源点，比如说求取最长路时图不联通的话，我们只需要加入一个点S，对其他的每个点建立一条权值为0的边图就联通了，然后从S点开始进行spfa判环。最短路类似。

3、  建好图之后直接spfa或bellman-ford求解，不能用dijstra算法，因为一般存在负边，注意初始化的问题。
--------------------- 
 

本博客有相关习题

一、预备知识

最短路基本性质

#define inf 0x3fffffff
#define M 1005	//最大点数

struct edge{
    int v, w, next;
}e[10005];		//估计好有多少条边

int pre[M], cnt, dist[M], n;
bool inq[M];
//注意初始化
void init ()
{
    cnt = 0;
    memset (pre, -1, sizeof(pre));
}
//注意双向加边 
void addedge (int u, int v, int w)    //加边函数，慢慢模拟就会明白的
{
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = pre[u];		//接替已有边
    pre[u] = cnt++;				//自己前插成为u派生的第一条边
}

void spfa (int u)
{
    int v, w, i;
    for (i = 1; i <= n; i++)	//对于从1到n的编号
        dist[i] = inf, inq[i] = false;
    dist[u] = 0;
    queue<int> q;
    q.push (u);
    inq[u] = true;
    while (!q.empty())
    {
        u = q.front();
        q.pop();
        inq[u] = false;
        for (i = pre[u]; i != -1; i = e[i].next)
        {
            w = e[i].w;
            v = e[i].v;
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
                if (!inq[v])
                {
                    q.push (v);
                    inq[v] = true;
                }
            }
        }
    }
}

如果图中不存在负权回路，则当算法结束以后，对于边 $<x,y>$ 有 $dis[y]\le dis[x]+w$ ，即 $dis[y]-dis[x]\le w$ 成立。

二、什么是差分约束系统

对于一组不等式：
$$\{\begin{array}{c}{x}_1-x_2\le 0\\ x_1-x_5\le 1\\ x_2-x_5\le 1\\ x_3-x_1\le 5\\ x_4-x_1\le 4\\ x_4-x_3\le -1\\ x_5-x_3\le -3\\ x_5-x_4\le -3\end{array}$$
特点是全都是两个未知数的差小于等于某个常数（大于等于也可以，因为左右乘 $-1$ 就可以化成小于等于的形式），这样的不等式组称作差分约束系统。

这个不等式组要么无解，要么就有无限组解。因为如果存在一组解 { x 1 , x 2 , . . , x n } \{x_1,x_2,..,x_n\} {x1​,x2​,..,xn​} 的话，那么对于任何一个常数 $k$ 有 { x 1 + k , x 2 + k , . . , x n + k } \{x_1+k,x_2+k,..,x_n+k\} {x1​+k,x2​+k,..,xn​+k} 也肯定是一组解，因为任何两个数加上一个数以后，它们之间的关系（差）是不变的，这个差分约束系统中的所有不等式都不会被破坏。

三、差分约束系统与最短路径

差分约束系统的解法用到了单源最短路径问题中的三角形不等式。即对有向图中任意一条边 $<u,v>$ 都有： $dis[v]\le dis[u]+len[u][v]$ ，其中 $dis[u]$ 和 $dis[v]$ 是从源点分别到点 $u$ 和点 $v$ 的最短路径的长度，$len[u][v]$ 是边 $<u,v>$ 的长度值。

这是显然的：如果存在顶点 $u$ 到顶点 $v$ 的有向边，那么从源点到顶点 $v$ 的最短路径长度 小于等于从源点到顶点 $u$ 的最短路径长度加上边 $<u,v>$ 的长度值。

显然上述的不等式就是所描述的，也和差分约束系统中的不等式相同，因此就可以把差分约束系统转化成一张图。

四、构图求解

4.1 基本构图

每个未知数 $x_i$ 对应图中的一个顶点 $v_i$ ，把所有的不等式都化成图中的一条边，对于不等式 $x_i-x_j\le y$ 化成三角形不等式 $x_i\le x_j+y$ 就可以化成边 $<v_j,v_i>$ 权值为 $y$ 。最后在这张图上求一遍单源最短路，这些三角不等式就全部满足了，因为它是最短路问题的基本性质。

不等式组 $(1)$ 转化成

4.2 求解

以 $1$ 为起点，则起点到各个顶点的最短距离为 $dis[1]=0,dis[2]=2,dis[3]=5,dis[4]=4,dis[5]=1$ 则得到解 $x_1=0,x_2=1,x_3=5,x_4=4,x_5=1$

以 $3$ 为起点，则起点到各个顶点的最短距离为 $dis[1]=-5,dis[2]=-5,dis[3]=0,dis[4]=-1,dis[5]=-4$ 则得到解 $x_1=-5,x_2=-4,x_3=0,x_4=-1,x_5=-4$

以不同顶点作为起点会得到不同的解，但这些解都一定合理。

• 什么情况下无解？ 存在负权回路！

4.3 增加源点

具体实现时，往往在原图上附加一个顶点，这个顶点与每个顶点都连接一条权值为 $0$ 的边，以上述不等式为例，也就是新加入一个未知数 $x_0$ ，然后对每个未知数都对 $x_0$ 加一个不等式，得到这样的不等式组 $(2)$ ，化成顶点图

图中每一条边都代表差分约束系统的一个不等式。现在以 $v_0$ 为源点，求单源最短路，最终得到的$v_0$ 到 $v_i$ 的最短路径长度就是 $x_i$ 的一个解。如图中 $v_0$ 到其他各个顶点的最短距离分别是 { − 5 , − 3 , 0 , − 1 , − 4 } \{-5,-3,0,-1,-4\} {−5,−3,0,−1,−4} ，因此满足上述不等式的一组解就是 { x 1 , x 2 , x 3 , x 4 , x 5 } = { − 5 , − 3 , 0 , − 1 , − 4 } \{x_1,x_2,x_3,x_4,x_5\}=\{-5,-3,0,-1,-4\} {x1​,x2​,x3​,x4​,x5​}={−5,−3,0,−1,−4} 。当然把每个数都加上 $10$ 也是一组解 { 5 , 7 , 10 , 9 , 6 } \{5,7,10,9,6\} {5,7,10,9,6} ，但是这组解只满足不等式组 $(1)$ ，也就是原先的差分约束系统，而不满足不等式组 $(2)$ ，也是我们后来加上的那些不等式。当然这是无关紧要的，因为 $x_0$ 本来就是个局外人，并不在乎它。

对于上面例子而言，它代表的解 $x_0$ 值也在其中也就是 $x_0=0$ 。但是 $x_0$ 的值是无可争议的，既然是以它作为源点求最短路径，那么源点到它的最短路径当然是 $0$ 了，因此，我们解这个差分约束系统无形中存在一个条件 $x_0=0$ ，那么它有什么用呢？可以限制所有的未知数的解都不大于0 。

• 一个有趣的结论：当我们一开始就把 $x_0$ 的解死定为 $A$ 的时候，所有未知数的解都不会大于 $A$ （一开始把 $dis[0]=A$）

五、例题

5.1 最大身高

Description

​ FJ的 $N(1\le N\le 10,000)$ 头奶牛站成一排，并从左到右被编号为 $1..N$ 。每头奶牛都有一个正整数的身高，具体的值FJ暂时保密，但会告诉你它们当中最高的一头的编号 $I$ 和身高 $H(1\le H\le 10^6)$ 的值。

​ FJ制作一张包含 $R(0\le R\le 10^4)$ 行的列表，每行的都是形如"第17号奶牛能看到第34号奶牛”，其意义是34号奶牛的身高不低于17号奶牛的身高，并且在17号和34号之间的奶牛的身高都严格低于17号奶牛的身高。

​ 请你确定奶牛每头奶牛的最大可能的身高，我们保证给出的数据都是正确的，并且一定有满足限制条件的解。

Input

​ 第1行：包含四个用空格分开的整数：N, I, H 和 R

​ 第2…R+1行：每行包含两个用空格分开的整数A和B(1 <= A,B <= N),表示奶牛A能看到奶牛B

Output

​ 第1…N行：第i行包含一个整数，表示第i头奶牛的最大身高。

Sample Input

9 3 5 5
1 3
5 3
4 3
3 7
9 8

Sample Output

5
4
5
3
4
4
5
5
5

Solution
$$\{\begin{array}{c}{x}_1-x_3\le 0\\ x_2-x_1\le -1\\ x_5-x_3\le 0\\ x_4-x_5\le -1\\ x_4-x_3\le 0\\ x_3-x_7\le 0\\ x_4-x_3\le -1\\ x_5-x_3\le -1\\ x_6-x_3\le -1\\ x_9-x_8\le 0\end{array}$$

5.2 糖果

Description

​ 幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

Input

​ 输入的第一行是两个整数N，K。

​ 接下来K行，表示这些点需要满足的关系，每行3个数字，X，A，B。

如果X=1，表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多；

如果X=2，表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果；

如果X=3，表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果；

如果X=4，表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果；

如果X=5，表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果；

Output

​ 输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出-1。

Sample Input

7 7
1 4 5
2 1 4
5 3 5
4 1 3
3 1 2
2 2 3
4 6 7

Sample Output

17

Solution

本题对于每个小朋友要求都能分到糖果，也就是说，每个小朋友的糖果数应该要大于 $1$ ，怎么把不等式组的解都变为 $\ge 1$ ？

• 重要结论：以 $x_i-x_j\le y$ 为约束条件，建图求最短路后得到的是最大解。所有的解都不大于且尽可能逼近 $dis[x_0]$ 。

若有 $x_i-x_j\le y$ 可在图中连一条 $x_j$ 出发指向 $x_i$ 的有向边，权值为 $y$ ，再添加一个源点 $x_0$ 指向各个顶点 $x_1,x_2,..,x_n$ 权值为 $0$ 。若一开始就把 $dis[x_0]$ 的值定死为 $A$ 再求最短路，那么求出来的解都是不大于 $A$ 且与 $A$ 接近的最大解，也就是 $x_i\le A$ ，那么我们设 $dis[x_0]=-1$ ，所有未知数解直接取绝对值，行吗？答案是它取绝对值以后不难满足不等式组 $(1)$ ，通过一些讨论发现，直接在所有未知数上加上某个常数来解决此题是不可行的。

正确接啊应该是，对于这题，按照相反的建图方式，

若有 $x_i-x_j\ge y$ 则在图中连上一条 $<x_j,x_i>$ 的有向边，权值为 $y$ ，再以 $x_0$ 为起点，求单源最长路(无正权环前提下)，求出的起点到各个点的距离就是不等式组 $(2)$ 的一组解。若一开始把 $dis[x_0]$ 定值为 $A$ 再求最长路，那么求出的其他点的 $dis[x_i]$ 的值一定不会小于 $A$ ，并且，求出的值是不小于它且最接近它的一组，也就是最小解。

六、总结

查分约束求解不等式组分为两种方法：最短路和最长路。

其中最短路对应最大解，最长路对应最小解，特别的，若有 $x_i=x_j$ 的情况，建图时候，从 $x_i$ 出发连一条权值为 $0$ 的边到 $x_j$ ，同时也建一条同等权值的反向边。

对于许多复杂的问题，我们通常选择将不够清晰、难以处理的模型转化为容易理解、易于处理的模型。就像用已知的知识作为工具去探索未知领域一样，联想、发散、转化将成为相当有用的武器。

差分约束系统

一、概念

二、引例

                                              

三、差分约束与最短路模型

1、与最短路模型的联系

先给出结论：求解差分约束系统，都可以转化成图论的单源最短路径（或最长路径）问题。

我们观察上面例子中的不等式，都是x[i] - x[j] <= a[k]，可以进行移项，成为x[i] <= x[j] + a[k]，我们令a[k] = w(j, i)，dis[i]=x[i],并使i=v,j=u,那么原始就变为：dis[u]+w(u,v)>=dis[v],于是可以联想到最短路模型中的一部分代码

if(dis[u]+w(u,v)<=dis[v])
{
    dis[v]=dis[u]+w(u,v);
}

这不正与松弛操作相似吗？

但是好像不等号方向刚好相反，但其实这并不矛盾

上面的代码要实现的是使dis[u]+w(u,v)>dis[v],而对于不等式，我们进行建边的操作：对于每个不等式 x[i] - x[j] <= a[k]，对结点 j 和 i 建立一条 j -> i的有向边，边权为a[k]，求x[n-1] - x[0] 的最大值就是求 0 到n-1的最短路，两者刚好吻合。所以求解差分约束问题就转化为了最短路问题。

2.问题解的存在性

    由于在求解最短路时会出现存在负环或者终点根本不可达的情况，在求解差分约束问题时同样存在

    （1）、存在负环

如果路径中出现负环，就表示最短路可以无限小，即不存在最短路，那么在不等式上的表现即X[n-1] - X[0] <= T中的T无限小，得出的结论就是 X[n-1] - X[0]的最大值不存在。在SPFA实现过程中体现为某一点的入队次数大于节点数。（貌似可以用sqrt(num_node)来代替减少运行时间）

     （2）、终点不可达

这种情况表明X[n-1]和X[0]之间没有约束关系，X[n-1] - X[0]的最大值无限大，即X[n-1]和X[0]的取值有无限多种。在代码实现过程中体现为dis[n-1]=INF。

3、不等式组的转化

做题时可能会遇到不等式中的符号不相同的情况，但我们可以对它们进行适当的转化

（1）方程给出：X[n-1]-X[0]>=T ,可以进行移项转化为： X[0]-X[n-1]<=-T。

（2）方程给出：X[n-1]-X[0]<T, 可以转化为X[n-1]-X[0]<=T-1。

（3）方程给出：X[n-1]-X[0]=T，可以转化为X[n-1]-X[0]<=T&&X[n-1]-X[0]>=T，再利用（1）进行转化即可

4、应用

对于不同的题目，给出的条件都不一样，我们首先需要关注问题是什么，如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成"<="的形式，建图后求最短路；相反，如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成">="，建图后求最长路。

5、相关题目链接

（1）、POJ 1716 Integer Intervals 

（2）、HDOJ 3666 THE MATRIX PROBLEM