算法学习笔记（差分约束系统）

前置：spfa

从例题入手：

【模板】差分约束系统 | StarryCoding

题目描述

给定$n$未知量和一个大小为$m$的不等式（或等式）组，请你判断这个不等式（或等式）组是否有解。

$1$ $i$ $j$ $z$：表示$x_i\le x_j+z$

$2$ $i$ $j$ $z$：表示$x_i\ge x_j+z$

$3$ $i$ $j$：表示$x_i=y_j$。

若存在解，输出$YES$。

若不存在解，输出$NO$。

输入描述

第一行一个整数$T$表示样例个数。$(1\le T\le 1000)$

对于每组样例：

第一行两个整数$n,m$。$(2\le n\le 5\times 10^3,1\le m\le 5\times 10^3)$

接下来$m$行，每行一个不等式组。$(1\le i,j\le n,1\le z\le 10^7)$

数据保证 $\sum n\le 5\times 10^3,\sum m\le 10^4$。

输出描述

对于每组样例，第一行输出$YES$或$NO$。

输入样例

23 3
1 1 2 3
1 1 3 3
2 1 3 43 3
1 1 2 3
1 1 3 3
2 1 3 3

输出样例

NO
YES

---

在我们的$spfa$中，当$d[y]>d[x]+w$时，我们就会更新$d[y]$，换句话说，若存在一条边连接着点$x$和$y$，则$d[y]<=d[x]+w$恒成立。而这个不等式就相当于题目中第一个不等式$x_i\le x_j+z$，这也就是差分约束的原理。

所以，对于$x_i\le x_j+z$，可以假定有一条权值为$z$的边从点$j$出发指向$i$。

那具体如何判断所给不等式组是否有解？可以拟定一个虚拟源点$0$，用边权为$0$的边连到所有节点。然后从这个虚拟源点出发跑一遍最短路，若出现负环，则不等式组无解，因为出现负环时，$0$到$i$的距离比$0$到$j$的距离更远，用公式来讲就是$d[i]>d[j]+z$即$x_i>x_j+z$，不符合题意。

对于第二个不等式$x_i\ge x_j+z$则变形为，$x_j\le x_i-z$。

对于第三个式子$x_i=y_j$，则在$x$和$y$之间建立一个边权为$0$的双向边。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
using ll = long long;
const ll inf = 2e18;struct Edge
{int x;ll w;
};int n, m;
vector<Edge> g[N];
ll d[N];bool spfa(int st)
{//两行初始化，不要忘记for(int i = 1; i <= n; ++i) d[i] = inf;d[st] = 0;queue<int> q;       //队列存储需要更新的点bitset<N> inq;      //inq[i]表示第i个点在不在队列中q.push(st);vector<int> cnt(n + 1);     //计数while(q.size())     {int x = q.front(); q.pop(); inq[x] = false;for(auto [y, w] : g[x])         //更新所有边{if(d[y] > d[x] + w)         //如果能被更新，更新且入队{if(++ cnt[y] >= n) return true;d[y] = d[x] + w;if(!inq[y]){q.push(y);inq[y] = true;}}}}return false;
}void solve()
{cin >> n >> m;for(int i = 0; i <= n; ++i) g[i].clear();for(int i = 1; i <= m; ++i){int op, x, y; cin >> op >> x >> y;if(op == 1){ll w; cin >> w;g[y].push_back({x, w});}if(op == 2){ll w; cin >> w;g[x].push_back({y, -w});}if(op == 3){g[y].push_back({x, 0});g[x].push_back({y, 0});}}for(int i = 1; i <= n; ++i) g[0].push_back({i, 0});if(spfa(0)) cout << "NO" << '\n';else cout << "YES" << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _; cin >> _;while(_--) solve();return 0;
}

最后因为不等式组的解不唯一，输出时挑一个满足题意的解，只需要将距离数组$d$输出即可。