前言

最近比较颓，把很多原本计划要干的事情咕掉了……

而今天，我终于找到了一个上午来补各种咕掉的东西。

于是乎，就有了这篇文章……

何为差分约束？

差分约束系统，即给出一组形如$x_u - x_v \geq d$或$x_u - x_v \leq d$的不等式，要求出该组不等式的一组解的问题。

差分约束的原理

回忆一下，我们在做图论算法中的单元最短路时，每一次松弛操作都是基于三角不等式的，即$dis_to < dis_from + w$

如果用代码表示的话，则是

if(dis[to] > dis[from] + w){
    dis[to] = dis[from] + w;
    //即每时每刻dis[to] <= dis[from] + w
}

移一下项，就变成了

dis[to] - dis[from] < w;

可以看出，这就是上面不等式的形式。

因此，我们可以把差分约束问题中的变量看做有向图中的点，将其不等关系看做有向图中的边，之后在图上跑一边单元最短路算法，即可求出该不等式组的一组解。

而如果图中存在负权环，则该不等式组无解。

实现方式

对于每个形如$x_u - x_v \leq w$的不等式，我们先对其移项，得到三角不等式的一般形式，即$x_u \leq x_v + w$。

之后我们连一条从$v$到$u$，权值为$w$的边，跑最短路即可。

如果是形如$x_u - x_v \geq w$的不等式，则我们可以选择将其化为$x_u \geq x_v + w$来跑最长路，或者将两边同时乘以$-1$，变为$x_v - x_u \leq w$来跑最短路。

每一次跑最短路时，需要先将起始点的dis设为0，其他点的dis初始化为一个极大值。

如果图中有负边权，则必须使用Bellman-Ford或SPFA来求解最短路。

若使用Bellman-Ford，则需要记录其松弛操作的次数。若当其在$n - 1$次松弛操作之后还可以松弛，则证明图中含有负权环，原不等式组无解。

若使用SPFA，则需要记录每个节点的入队次数。若有一个节点入队超过$n$次，则证明图中含有负权环，原不等式组无解。

若最后的跑出来的dis值为刚开始的极大值，则证明两点直接没有任何约束关系。这时的解是无限多的。

其他技巧

在跑单元最短路之前，我们需要建立一个连接了所有点的超级原点跑一遍最短路，以保证图的联通性。

若题目中要求求出两个变量之差的最大值，则必须将不等式转换为$x_u - x_v \leq w$的形式来跑最短路。

反之，则必须转换为$x_u - x_v \geq w$的形式来求最长路。

例题

LuoguP4878-【USACO】布局

给出 $n$ 个形如$x_u - x_v \geq d$或$x_u - x_v \leq d$，求一组使$x_1$与$x_n$差最大的解，输出最大差值。

若无解，请输出 -1，若 $x_1$ 与 $x_n$ 的差为无限大则输出 -2。

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 150001

using namespace std;

int n , ml , md;

struct Edge{
    int to;
    int last;
    ll dis;
}edge[N << 1];

int edge_num;
int head[N << 1];

I void add_edge(int from , int to , ll dis){
    edge[++ edge_num] = (Edge){to , head[from] , dis};
    head[from] = edge_num;
}

ll dis[N] , cnt[N];
bool vis[N] , flag = false;

int SPFA(int s){
	queue<int > Q;
    for(int i = 1;i <= n;i ++){
        dis[i] = 0x3f3f3f3f;
    }
    dis[s] = 0;
    Q.push(s);
    vis[s] = true;
    int first;
    while(!Q.empty()){
        first = Q.front();
        Q.pop();
        vis[first] = false;
        for(int i = head[first]; i ; i = edge[i].last){
            if(dis[edge[i].to] > dis[first] + edge[i].dis){
            	dis[edge[i].to] = dis[first] + edge[i].dis;
                if (++ cnt[edge[i].to] >= n){   //如果形成负权回路，证明不存在可行路径。
                    return -1;
                }
                if(vis[edge[i].to] == false){
                    vis[edge[i].to] = true;
                    Q.push(edge[i].to);
                }
            }
        }
    }
    if(dis[n] == 0x3f3f3f3f){
        return - 2;
    }
    else{
        return dis[n];
    }
}

int main(){
    int u , v , d;
    scanf("%d%d%d" , &n , &ml , &md);
    for(int i = 1; i <= ml; i ++){ 
        scanf("%d%d%d" , &u , &v , &d);
        add_edge(u , v , d);   //dis[u] <= dis[v] + d
    }
    for(int i = 1; i <= md; i ++){
        scanf("%d%d%d" , &u , &v , &d);
        add_edge(v , u , -d);   //dis[v] <= dis[u] - d
    }
    for(int i = 1; i <= n; i ++){
        add_edge(0 , i , 0);    //建立超级原点，判断图的联通性
    }
    int sb = SPFA(0);
    if(sb <= -1){   
        cout << sb << "\n";
    }
    else{
        cout << SPFA(1) << "\n";
    }
   return 0;
}