差分约束

差分约束是一种特殊的N元一次不等式，它包含N个变量X1~Xn以及M个约束条件，每个约束条件都是由两个变量作差构成的，形如Xi－Xj≤Ck，其中Ck是常数（正负均可），1≤i，j≤N，1≤k≤M。我们要解决的问题就是，求一组解X1=a1，X2=a2······Xn=an，使所有的约束条件得到满足。

一、引例

1、一类不等式组的解
给定n个变量和m个不等式，每个不等式形如 x[i] - x[j] <= a[k] (0 <= i, j < n, 0 <= k < m， a[k]已知)，求 x[n-1] - x[0] 的最大值。例如当n = 4，m = 5，不等式组如图一-1-1所示的情况，求x3 - x0的最大值。

观察x3 - x0的性质，我们如果可以通过不等式的两两加和得到c个形如 x3 - x0 <= Ti 的不等式，那么 min{ Ti | 0 <= i < c } 就是我们要求的x3 - x0的最大值。于是开始人肉，费尽千辛万苦，终于整理出以下三个不等式：
1. (3) x3 - x0 <= 8
2. (2) + (5) x3 - x0 <= 9
3. (1) + (4) + (5) x3 - x0 <= 7
这里的T等于{8， 9， 7}，所以min{ T } = 7，答案就是7。的确是7吗？我们再仔细看看，发现的确没有其它情况了。那么问题就是这种方法即使做出来了还是带有问号的，不能确定正确与否，如何系统地解决这类问题呢？
2、最短路
让我们来看另一个问题，这个问题描述相对简单，给定四个小岛以及小岛之间的有向距离，问从第0个岛到第3个岛的最短距离。如图一-1-2所示，箭头指向的线段代表两个小岛之间的有向边，蓝色数字代表距离权值。
如图：

这个问题就是经典的最短路问题。由于这个图比较简单，我们可以枚举所有的路线，发现总共三条路线，如下：
1. 0 -> 3 长度为8
2. 0 -> 2 -> 3 长度为7+2 = 9
3. 0 -> 1 -> 2 -> 3 长度为2 + 3 + 2 = 7
最短路为三条线路中的长度的最小值即7，所以最短路的长度就是7。这和上面的不等式有什么关系呢？还是先来看看最短路求解的原理，看懂原理自然就能想到两者的联系了。但就算知道了也干不起题

二、算法简介与分析

差分约束系统的每一个约束条件Xi－Xj≤Ck可以变形为Xi≤Xj＋Ck。这与单源最短路中的bellman—ford算法中的三角形不等式dis[v]≤dis[u]＋w(u,v)非常相似。因此，可以把每个变量Xi看做有向图中的一个节点i，对于每一个约束条件Xi－Xj≤Ck，从节点j向节点i连一条长度为Ck的边。
而由于查分约束的原式是n元一次不等式，从数学上可以推到——差分约束系统的解有三种情况：1、有解；2、无解；3、无限多解。
1、我们在学习最短路的时候，会出现负权圈或者根本就不可达的情况，所以在不等式组转化的图上也有可能出现上述情况，先来看负权圈的情况，如图，下图为5个变量5个不等式转化后的图，需要求得是X[t] - X[s]的最大值，可以转化成求s到t的最短路，但是路径中出现负权圈，则表示最短路无限小，即不存在最短路，那么在不等式上的表现即X[t] - X[s] <= T中的T无限小，得出的结论就是 X[t] - X[s]的最大值 不存在。

2、 再来看另一种情况，即从起点s无法到达t的情况，如图，表明X[t]和X[s]之间并没有约束关系，这种情况下X[t] - X[s]的最大值是无限大，这就表明了X[t]和X[s]的取值有无限多种。

需要注意的是，如果{A1，A2，A3，·······，An}是一组解，那么对于任意的常数d，{A1＋d，A2＋d，A3＋d，······，An＋d}一定也是一组解（这个性质具体有什么用会在后面的例题中说道）

并且，在某些题目中，约束条件形如Xi－Xj≥Ck。我们还是可以看成从i到j有一条长度为Ck的有向边，只是改为计算单源最长路，若存在正环则无解。当然，我们也可以把不等式变为Xj－Xi≤﹣Ck，再进行如上的差分约束。

如果给出的不等式有"<=“也有”>="，又该如何解决呢？很明显，首先需要关注最后的问题是什么，如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成"<=“的形式，建图后求最短路；相反，如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成”>="，建图后求最长路。
如果有形如：A - B = c 这样的等式呢？我们可以将它转化成以下两个不等式：
A - B >= c (1)
A - B <= c (2)
再通过上面的方法将其中一种不等号反向，建图即可。
最后，如果这些变量都是整数域上的，那么遇到A - B < c这样的不带等号的不等式，我们需要将它转化成"<=“或者”>="的形式，即 A - B <= c - 1。

三、差分约束的经典应用

【例题一】（区间约束）
题目描述
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1…N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

写一个程序完成以下工作：

输入格式
第一行包含数据N，区域的个数(0<N≤30000)；

第二行包含H，房子的数目(0<H≤5000)；

下面的H行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。

输出格式
输出文件只有一行写有树的数目

输入输出样例
输入
9
4
1 4 2
4 6 2
8 9 2
3 5 2

输出
5

本题思路
这题并不能直接套上面所说的算法，但是可以转换成上面的形式：

[l, r]至少要种T棵树 可以转换为Sum® - Sum(l-1) >= T

（sum_i是前缀和，即从1到i有多少棵树）

答案倒不是求这个前缀和序列(没意义)，只要dis(N)

转换完，就可以用上面的方法求解了：

先乘-1，转换成Sum(l-1) - Sum® <= -T

于是r向l-1连一条长度为-T的边（明白前缀和就知道为什么是l-1而不是l了）

查看之前关于源点的约定，放到这里意思是：Sum(i) - Sum(0) <= 0

显然是错的，那就把N+1当作源点，把所有结点连到N+1，就行了

还有两个条件，即：

Sum(i) - Sum(i-1) <= 1

Sum(i-1) - Sum(i) <= 0

也要按照这两个条件加边

差分约束规定的只是元素的相对关系，按照题意 相对关系不变时最后的答案尽可能小

因此答案是dis(N) - min_dis,（min_dis是0~N最小的dis）也就是让min_dis=0(不种树)

举个例子好理解一点.比如N=4，下面是dis数组0~N

2, 2, 3, 5, 6

让它们都减去2，相对关系不变（就是上面提到过的那个性质）

0, 0, 1, 3, 4

这才是最优的解.

（dis有可能跑成负数，也不影响最后答案）

dis(N)是6-2=4，所以之前的Sum(N)就是4，答案也就是4了.

代码实现：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define MAXN 30010
#define MAXM 100010

struct Edge {
    int next, to, w;
} edge[MAXM];
int head[MAXN], cnt;

void Add(int u, int v, int w) 
{
    edge[++cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
    edge[cnt].to = v;
}
//用链式前向星存图
int N, M;
int dis[MAXN];
bool vis[MAXN];

void SPFA(int S) //SPFA模版
{ 
    queue<int> Q;
    Q.push(S);
    for(int i=0; i<=N+1; i++) dis[i] = 1e9;
    dis[S] = 0;
    vis[S] = 1;
    while(!Q.empty()) 
    {
        int k = Q.front();
        Q.pop();
        vis[k] = 0;
        for(int i=head[k]; i!=-1; i = edge[i].next) 
        {
            int to = edge[i].to;
            if(dis[to] > dis[k] + edge[i].w) 
            {
                dis[to] = dis[k] + edge[i].w;
                if(!vis[to]) 
                {
                    Q.push(to);
                    vis[to] = 1;
                }
            }
        }
    }
}

int main() {
    int x, y, t, S;
    cin >> N >> M;
    S = N+1; //源点为N+1 
    memset(head, -1, sizeof(head));
    for(int i=0; i<=N; i++) Add(S, i, 0); //Sum(i) - Sum(N+1) <= 0
    for(int i=1; i<=M; i++) 
    {
        cin >> x >> y >> t;
        Add(y, x-1, -t); //Sum(x-1) - Sum(y) <= -t
    }
    for(int i=1; i<=N; i++) 
    {
        Add(i-1, i, 1); //Sum(i) - Sum(i-1) <= 1
        Add(i, i-1, 0); //Sum(i-1) - Sum(i) <= 0
    }
    SPFA(S);
    int _min = 1e9;
    for(int i=0; i<=N; i++) _min = min(_min, dis[i]);
    cout << dis[N] - _min << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

提高题目：照片（也是很基础的 ）

【例题二】（线性约束）

题目描述
德黑兰的一家超市每天24小时营业，需要一些收银员才能满足其需求。超市经理雇用你来帮助他，解决他的问题。问题是超市在每天的不同时间需要不同数量的收银员（例如，午夜后的几个收银员，下午的许多收银员）以便为其客户提供良好的服务，并且他希望雇用最少数量的收银员。这个工作的收银员。
经理为您提供了当天每一小时所需的最少数量的收银员。该数据以R（0），R（1），…，R（23）给出：R（0）表示从午夜到凌晨1:00需要的最少收银员数量，R（1）显示此数字持续时间为凌晨1:00至凌晨2:00，依此类推。请注意，这些数字每天都相同。这项工作有N名合格的申请人。每个申请人我每24小时不停地工作一次从指定的小时开始正好8小时，例如ti（0 <= ti <= 23），恰好是从所提到的小时开始。也就是说，如果第i个申请人被雇用，他/她将从时间开始工作8小时。收银员不会互相替换，并且按照计划完成工作，并且有足够的收银机和柜台供雇用的人使用。

您要编写一个程序来读取R（i）的i = 0 … 23和ti的i = 1 … N，它们都是非负整数并计算最小数量需要雇用收银员来满足上述限制。请注意，可以有比特定插槽所需的最少数量更多的收银员。

输入格式

第一行输入是此问题的测试用例数（最多20个）。每个测试用例以24个整数开始，表示一行中的R（0），R（1），…，R（23）（R（i）可以是至多1000）。然后在另一行中有N个申请人数（0 <= N <= 1000），之后是N行，每行包含一个ti（0 <= ti <= 23）。测试用例之间没有空行。

输出格式

对于每个测试用例，输出应写在一行中，这是所需的收银员数量最少。

如果测试用例没有解决方案，则应该针对该情况编写无解决方案。

样本输入

1
1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
5
0
23
22
1
10

样本输出

1

解题思路
首先我们根据题意很容易 想到如下的不等式模型：
num[i]为i时刻能够开始工作的人数，x[i]为实际雇佣的人数，那么就有x[i]≤num[i]。
设r[i]为i时刻至少需要工作的人数，而每个员工可以工作8小时（我也要每天只工作8小时，55~），就可以推出：x[i-7]+x[i-6]+x[i-5]+x[i-4]+x[i-3]+x[i-2]+x[i-1]+x[i]≥r[i]
然后利用前缀和来优化算，设s[i]=x[1]+x[2]+x[3]+······+x[i]，由此可以推到：
0≤s[i]-s[i-1]≤num[i]，0 ≤ i ≤ 23，
s[i]－s[i-8]≥r[i]，8 ≤ i ≤ 23，
s[23]－s[i+16]+s[i]≥r[i]，0≤i≤7 （隔夜的情况）
由于最后这个表达式并不是标准的表达式，我们就可以把它整理成：s[i]－s[i+16]≥r[i]－s[23]
然后建图，枚举s[23]即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define maxn 300000
int cnp = 1, head[maxn], num[maxn];
int R[maxn], dis[maxn], in[maxn];
bool vis[maxn];

struct edge
{
    int to, last, co;
}E[maxn];

int read()
{
    int x = 0, k = 1;
    char c;
    c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

void add(int u, int v, int w)
{
    E[cnp].to = v, E[cnp].co = w;
    E[cnp].last = head[u], head[u] = cnp ++;
}

bool spfa()
{
    queue <int> q;
    for(int i = 1; i <= 30; i ++)
        dis[i] = -99999999;
    memset(vis, 0, sizeof(vis));
    memset(in, 0, sizeof(in));
    dis[0] = 0, q.push(0);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = 0;
        for(int i = head[u]; i; i = E[i].last)
        {
            int v = E[i].to;
            if(dis[v] < dis[u] + E[i].co)
            {
                dis[v] = dis[u] + E[i].co;
                if(!vis[v])
                {
                    if(++ in[v] == 26) return 1;
                    vis[v] = 1; q.push(v);
                } 
            }
        }
    }
    return 0;
}

void Build(int mid)
{
    memset(head, 0, sizeof(head)); cnp = 1;
    for(int i = 1; i <= 24; i ++)
    {
        add(i - 1, i, 0);
        add(i, i - 1, -num[i]);
    }
    for(int i = 8; i <= 24; i ++)
        add(i - 8, i, R[i]);
    for(int i = 1; i < 8; i ++)
        add(i + 16, i, R[i] - mid);
    add(0, 24, mid); 
}

int main()
{
    int T = read();
    while(T --)
    {
        for(int i = 1; i <= 24; i ++) R[i] = read();
        int n = read();
        memset(num, 0, sizeof(num));
        for(int i = 1; i <= n; i ++)
        {
            int x = read();
            num[x + 1] ++;
        }
        Build(n);
        if(spfa())
        { 
            printf("No Solution\n");
            continue;
        }
        int l = 0, r = n, ans;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            Build(mid);
            if(spfa()) l = mid + 1;
            else ans = mid, r = mid - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103