前言

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

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

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


何为差分约束?

差分约束系统,即给出一组形如$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-FordSPFA来求解最短路。

若使用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;
}

THE END