[数据结构与算法]差分约束系统详解

差分约束系统

什么是差分约束系统

差分约束系统指的是解决如下的多元一次不等式组的一种方法，其中(y₁,y₂…y_n是常数)，叫做差分的原因是多元一次不等式组的每一个不等式都是关于两个自变量做差的关系

一般有两种问法：

• 求一组满足条件的(x₁,x₂,…x_n)的解
• 求满足条件的某个x或者某些x的最大值或者最小值

求一组满足条件的(x₁,x₂,…x_n)的解

关于这个不等式组，可以发现要么是无解，要么是无限解，因为如果存在一组解满足不等式组，那对所有的x进行加上或减去一个相同的数，是一定可以满足不等式组的

Q：那怎么求解？

这里我们拿一个不等式出来看看：$x_i?x_j<=c$

移项化简的： $x_i<=x_j+c$

可以发现这个形式和最短路的松弛操作差不多，以不等式的形式写出来就是: $dis[i]<=dis[j]+c$，相当于在j到 i之间建立一条权值为c的边，这样求最短路后一定会满足 $dis[i]<=dis[j]+c$,因为它是最短路径问题的基本性质，所以我们可以将所有的不等式以连边的方式建成一个图，在这个图上面跑一个单源最短路就行

Q：单源最短路，那源点是谁？

为了保证所有的不等式都被满足，也就是所有的边必须被遍历到，我们需要建立一个超级源点0或者n+1，把他作为源点，而他必须和所有的点连一条权值为0的边，也就是dis[i] <= dis[0] + 0，0号点并非所需要的点，所以不管dis[0]的取值是多少，对于无解的情况都还是无解，对于有解的情况，我们上面讲过了，改变相对大小是无所谓的，一般来说我们会让dis[0] = 0,如果题目需要解的大小是大于等于0的，我们只需要从1到n中取最小值，将所有的点的值减去最小值就行

Q：什么时候无解？

先说结论：出现负环就代表无解

我们来证明一下：

假设现在有如下的一个堆条件：
$$\begin{gathered} x1<=x2+c1 \\ x2<=x3+c2 \\ ... \\ xn<=x1+cn \end{gathered}$$
我们进行不等式的放缩可以得到：
$$\begin{gathered} x1<=x1+\sum _{i=1}^n{c}_i \\ 即\sum _{i=1}^n{c}_i>=0 \end{gathered}$$
这是我们根据不等式得到的一个条件，显然我写的这个不等式是一个环，环的权值和是 ${\sum }_{i=1}^n{c}_i$，如果存在负环则不符合条件，就无解

Q：解题步骤？

• 将输入的条件，转换成形如 $x_v<=x_u+c$的形式，然后建一条从u指向v的权值为c的边
• 取一个超级源点0，建一条从0 指向i权值为 0的边，1<=i<=n
• 跑SPFA，如果有负环就说明无解，否则输出dis[i]

我们拿一个板子题看看代码怎么写

P5960 【模板】差分约束算法

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
int a, b, c;
int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}
bool vis[MAX];
int dis[MAX];
int cnt[MAX];
void SPFA(){
    queue<int>q;
    for(int i = 1; i <= n; ++i){
        vis[i] = 1;
        q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                cnt[v] = cnt[u] + 1;
                if(cnt[v] >= n){//负环
                    cout << "NO" << endl;
                    return;
                }
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i)cout << dis[i] << ' ';
    cout << endl;
}

void work(){
    cin >> n >> m;
    while (m--) {
        cin >> a >> b >> c;
        add(b, a, c);
    }
    SPFA();
}

int main(){
    io;
    work();
    return 0;
}

求满足条件的某个x或者某些x的最大值或者最小值

一般来说第一种情况比较简单，也比较板子，所以在这个的基础上，会产生一些限制，比如dis[0] = w等有一个未知数确定的情况，这样建立超级源点后，得到的其实是 $x_1,x_2,...,x_n<=w$的一组解，有了这个条件的限制后，通过跑最短路是可以获得在$x_1,x_2,...,x_n<=w$ 条件下的解的最大值。

证明如下：

举个例子：
$$\begin{gathered} x_1<=x_2+2 \\ {x}_1<=x_2+3 \\ {x}_1<=x_2+4 \\ x2=0 \end{gathered}$$
跑最短路后的结果是 $x_1<=2$，这显然是 $x_1$的最大值，x1只能取小于等于2的值，那2就是最大值

Q：那求最小值怎么办？

我们只需要将不等式进行移项构造出>=的情况即可跑一次最长路
$$\begin{gathered} x_1<=x_2+c_1转换为x_2>=x_1?c_1 \\ {x}_2<=x_3+c_2转化为x_3>=x_2?c_2 \\ ... \\ {x}_n<=x_1+c_n转换成x_1>=x_n?c_n \end{gathered}$$

$x_v>=x_u?c$可以转换成最长路中建一条从u到v建一条权值为-c的边

跑最长路就可以，如果存在正环就说明无解

Q：如何解题：

• 先题目要求是求最小值还是最大值

• 如果是求最小值，就说明是跑最长路，我们就构造出>=的不等式

  如果是求最大值，就说明是跑最短路，我们就构造出<=的不等式

• 再建立超级源点，跑最短路或最长路，注意无解的情况

P6145 [USACO20FEB]Timeline G

题目描述：

在m天内进行了n次挤奶，第i次挤奶不早于 Si天，另外有c个要求(a, b, x),含义是第b次挤奶在第a次挤奶结束至少x天后

问每次挤奶的最早日期是什么

思路：

首先，看见最早日期，就是求最小值，就是跑最长路，所以要建立>=的不等式

第一个条件转换成不等式是： $dis[i]>=S_i$

第二个条件转换成不等式是：$dis[b]>=dis[a]+x$

我们可以建立一个超级源点0,dis[0] = 0,这样第一个条件就可以转换成 $dis[i]>=dis[0]+S_i$，可以看作从0到i建了一条权值为Si的边，第二个条件可以看出从a到b建立了一条权值为x的边，然后跑最长路即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, s;
int a, b, c;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

ll dis[MAX];
bool vis[MAX];

void SPFA(){
    queue<int>q;
    mem(dis, -inf);
    q.push(0);dis[0] = 0;vis[0] = 1;
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] < dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i)cout << dis[i] << endl;
}

void work(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++i){
        cin >> s;
        add(0, i, s);
    }
    while (k--) {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    SPFA();
}

int main(){
    io;
    work();
    return 0;
}

总结

• 查分约束难在建图

• 求最大值时跑最长路，转换成>=的形式

  求最小值时跑最短路，转换成<=的形式

• 跑最短路时存在负环是无解

  跑最长路时存在正环是无解

• 特殊的建图方法：

  设a[i]是第i位置的值，求前缀和sum[i] = sum[i - 1] + a[i]，可以实现关于区间权值的不等式的建图，这时，有一个最基本的关系是:$0<=sum[i]?sum[i?1]<=1$，其他的关系就要根据题目去探索了

• 单单出现等于号的情况要注意，要建立双向边，比如：$x1=x2+c$，要转换成x1<=x2+c和x2<=x1-c等不等式，具体用小于号还是大于号还是得看题目要求