[链接登录后可见]
一.什么是差分约束系统
差分约束系统用来解决形似如下的一组不等式：
$$
\begin{cases}
\ x_ {c_ 1}-x_ {c'_ 1}\leq y_ 1
\ x_ {c_ 2}-x_ {c'_ 2} \leq y_ 2
\ \cdots
\ x_ {c_ m} - x_ {c'_ m}\leq y_ m
\end{cases}
$$
这一种不等式的特点为：
$1.$ 两个数的差小于等于某一个常数。
$2.$ 对于结果，只有两种情况：无解 或 有无数组解。
对于第一个特点，我们同样可以处理大于等于的情况。
处理方法，留在下文讲解。
二.差分约束系统和单源最短路径的关系
在单源最短路径中，任何一条边都满足三角形不等式。
即： $dis_ u \leq dis_ v + w$。
那我们往最上面的不等式看，也就是：
$x_ i - x_ j \leq k$。
我们可以将其变化一下，转化为：
$x_ i \leq x_ j + k$。
这样我们就很容易看出，转化后的不等式与单源最短路径中的三角形不等式十分相似。
那么这样，就可以使用单源最短路径算法来实现差分约束系统。
三.算法实现步骤
在每一个不等式中，都可以用一个点来表示不等式的未知数。
对于不等式 $x_ i - x_ j \leq k$，上文中提到可以转换为$x_ i \leq x_ j + k$，也就是说，我们可以在 $i->j$ 连接一条边权为 $k$ 的边。
这样就可以很方便的建图，从每个点跑一次单源最短路径，这样就可以得到解，虽然每个点得到的解可能不相同，但是都是正确的。
但是！
我们需要的解肯定是统一的。
那我们该怎么办呢？
我们可以创建一个超级源点$0$ ，将所有点与其连边。
于是这样，我们就可以从源点 $0$ 跑一次单源最短路径。
当然，如果要求得到最大解，我们大可以采用单源最长路径。
拓展：
很多情况题目给出的约束条件没有那么方便让我们操作。
有两种可能：
$1.$ 对于 $x_ i - x_ j \geq k$ 的情况，我们可以乘以 $-1$，将符号颠倒处理即可。
$2.$ 对于 $x_ i - x_ j = k$ 的情况，我们可以将此不等式拆分成 $2$ 个约束条件：① $x_ i - x_ j \leq k$ ②$x_ i - x_ j \geq k $ 。这样操作就可以了。
四.例题讲解
例题目录：
$1.$ [链接登录后可见]
$2.$ [链接登录后可见]
$3.$ [链接登录后可见]
$4.$ [链接登录后可见]
$5.$ [链接登录后可见]
$6.$ [链接登录后可见]
步入正题！
这道题是差分约束系统的模板题。
题意已经很简洁了，不等式也化为了 $x_ i - x_ j \leq k$ 的形式。
对于无解的情况，只要一个点入队次数大于 $n+1$ 次时，那么就出现了负环。
对于判断负环，可以先完成此模板题[链接登录后可见]
。
出现了负环的情况，那么就是无解，为什么呢？
显然，我们是跑单源最短路径。那么，在负环的情况下，我们就会一直跑一直跑，会达到 $-\infty$ ，这样自然无解。
然后，那为什么我们要判断入队次数大于 $n+1$ 次而不是 $n$ 次而不是别的次数呢？
我们知道，图中原有 $n$ 个点，如果有解，也就是没有负环的情况，一个点最多只能遍历 $n$ 个点。
但是为什么是判断入队次数 $n+1$ 次呢？？？
不要忘记，在处理差分约束系统时，我们创建了一个超级源点$0$， 所以，图上的点变成了 $n+1$ 个。
那么这样，我们只要从超级源点 $0$ 开始跑单源最短路径，就可以完成这一道模板题了。
Code：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
const int N = 15555;
const int inf = 0x3f3f3f3f;
struct DAG {
int nxt;
int to;
int w;
}e[N];
int edge_ num = 0, head[N], n, m;
inline void add_ edge (int x, int y, int z) {
e[++edge_ num].nxt = head[x];
e[edge_ num].to = y;
e[edge_ num].w = z;
head[x] = edge_ num;
//链式前向星建图
}
int dis[N], num[N];//num[i]表示点i的入队次数
bool inque[N];//标记该点是否在队列中
bool SPFA (int x) {
queue<int> q;
q.push(x);//先把操作的点入队
num[x] ++; //该点入队次数++
memset (dis, inf, sizeof(dis));//最短路径长度全部设为正无穷
dis[x] = 0;//该点的与0的最短路径长度设为0
inque[x] = true;//标记该点在队中
while (!q.empty()) {//队列非空时进行操作
int u=q.front();//取出队头
q.pop();//记得弹出该点
inque[u] = false;//标记该点已不在队中
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] > dis[u] + e[i].w) {//三角形不等式
dis[v] = dis[u] + e[i].w;//更新
if (inque[v] == false) {//不在队列中的情况
q.push (v);//将该点入队
inque[v] = true;//标记该点在队中
num[v] ++;//该点入队次数增加1
if (num[v] == n + 1) {//如果该点入队次数达到n+1
//那么则出现了负环，返回false
return false;
}
}
}
}
}
return true;//千万不要忘了！！！
}
int main() {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= m; i ++) {
int u, v, w;
scanf ("%d%d%d", &u, &v, &w);
add_ edge (v, u, w);
//我们的不等式是x[u]-x[v]<=w
//所以连一条v->u边权为w的边权
}
for (int i = 1; i <= n; i++) {
add_ edge (0, i, 0);
//建超级源点0，所有点与0连接一条边权为0的边
}
if (SPFA(0) == false) {
puts ("NO");
//从0开始跑单源最短路径，有负环则输出NO
}
else {
//无负环输出每个点的最短路径长度
for (int i = 1; i <= n; i ++) {
printf ("%d ", dis[i]);
}
}
return 0;
}
既然在上文的差分约束系统模板中我们提到了负环判断，那么我们就顺手将判断负环模板做了。
按照题意，有的边是建双向边，有的边是建单向边。
我们没有必要建超级源点 $0$ ，也就是说，在判断负环时，该点入队次数在大于 $n$ 时就是负环了。
但是
请注意，该题有多组数据，所以在每一测之前都要清空数据。
到此，这题的注意点就没有了，具体实现可看代码。
Code：
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 155555;
const int inf = 0x3f3f3f3f;
struct EDGE {
int nxt;
int to;
int w;
}e[N<<1];
int head[N], edge_ num = 0, n, m;
bool inque[N];
int num[N], dis[N];
inline void clear() {//多测的清空操作
for (int i = 1; i <= m;i ++) {
e[i].nxt = 0;
e[i].to = 0;
e[i].w = 0;
edge_ num = 0;
head[i] = 0;
}
memset (num, 0, sizeof(num));
memset (dis, inf, sizeof(dis));
memset (inque, false, sizeof (false));
}
inline void add_ edge (int x, int y, int z) {
e[++edge_ num].nxt = head[x];
e[edge_ num].to = y;
e[edge_ num].w = z;
head[x] = edge_ num;
}
queue<int> q;
void SPFA (int x) {
q.push (x);//入队
dis[x] = 0;
num[x] ++;//入队次数++
inque[x] = true;//标记入队
while (!q.empty()) {
int u = q.front();//取队首
q.pop();//出队
inque[u] = false;//出队后的标记
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] > dis[u] + e[i].w) {//满足三角形不等式
dis[v] = dis[u] + e[i].w;//更新
if (inque[v] == false) {//若v点不在队中
q.push (v);//将v点入队
inque[v] = true;//标记入队
num[v] ++;//入队次数加一
if (num[v] >= n) {
//入队次数大于n次时
puts("YES");
return;
}
}
}
}
}
puts("NO");
return;
}
int main() {
int T;
scanf ("%d", &T);
while (T--) {
scanf ("%d%d", &n, &m);
clear();//多测一定要清空
for (int i = 1; i <= m; i ++) {
int x, y, z;
scanf ("%d%d%d", &x, &y, &z);
//按照题意建图
if (z>=0) {
add_ edge (x, y, z);
add_ edge (y, x, z);
}
else {
add_ edge (x, y, z);
}
}
SPFA(1);//没有必要建超级源点，直接从1开始单源最短路径
}
return 0;
}
往题目一看，映入眼帘 $3$ 个条件。
这题的难点再与如何把题目中给出的条件转化为我们建边的操作。
我们可以将这三个条件转化为下面三个（不）等式：
$1.$ $x_ a - x_ b \geq c$
$2.$ $x_ a - x_ b \leq c$
$3.$ $x_ a - x_ b = c$
上文我们说到过，对于 $x_ i - x_ j = k$ 的情况，我们可以将此不等式拆分成 $2$ 个约束条件：① $x_ i - x_ j \leq k$ ②$x_ i - x_ j \geq k $ 。
对于第一个不等式，我们将其乘以 $-1$ ，变形为：
$x_ b - x_ a \leq -c$
而第二个不等式已经符合我们建图的条件了。
于是，第一个约束条件我们建一条 $a->b$ 边权为 $-c$ 的边。
而第二个约束条件，我们建一条 $b->a$ 边权为 $c$ 的边。
而这道题更加简单，我们只要从超级源点 $0$ 开始跑单源最短路径，再判断是否有负环，就可以做出此题了。
Code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 155555;
const int inf = 0x3f3f3f3f;
struct DAG {
int nxt;
int w;
int to;
}e[N<<1];
int num[N], head[N], edge_ num = 0, n, m;
inline void add_ edge (int x, int y, int z) {
e[++edge_ num].nxt = head[x];
e[edge_ num].to = y;
e[edge_ num].w = z;
head[x] = edge_ num;
}
bool inque[N];
int dis[N];
inline bool SPFA (int x) {
queue<int> q;
q.push(x);//先把操作的点入队
num[x] ++;//入队次数++
memset (dis, inf, sizeof(dis));//最短路径长度全部设为正无穷
dis[x] = 0;//该点的与0的最短路径长度设为0
inque[x] = true;//标记该点在队中
while (!q.empty()) {//队列非空时进行操作
int u=q.front();//取出队头
q.pop();//记得弹出该点
inque[u] = false;//标记该点已不在队中
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] > dis[u] + e[i].w) {//三角形不等式
dis[v] = dis[u] + e[i].w;//更新
if (inque[v] == false) {//不在队列中的情况
q.push (v);//将该点入队
inque[v] = true;//标记该点在队中
num[v] ++;//该点入队次数增加1
if (num[v] == n + 1) {//如果该点入队次数达到n+1
//那么则出现了负环，返回false
return false;
}
}
}
}
}
return true;//千万不要忘了！！！
}
int main() {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= m; i ++) {
int op, a, b, c;
scanf ("%d%d%d", &op, &a, &b);
if (op == 1) {
scanf ("%d", &c);
add_ edge (b, a, -c);
}
if (op == 2) {
scanf ("%d", &c);
add_ edge (a, b, c);
}
if (op == 3) {
add_ edge (a, b, c);
add_ edge (b, a, c);
}
}
for (int i = 1; i <= n; i ++) {
//所有点与超级源点0连边
add_ edge (0, i, 0);
}
if (SPFA(0) == false) {
//有负环无解
puts("No");
}
else {
puts("Yes");
}
return 0;
}
在上文中我们提到，当不等式形式为 $x_ i - x_ j \geq k$ 时，我们将其乘以 $-1$，使其符号颠倒。
同样的，我们还有一种处理方法。
对于$x_ i - x_ j \geq k$ ，我们同样可以建一条 $j->i$ 边权为 $k$ 的边，但是我们要跑最长路径。
更改仅仅在于三角形不等式时，将大于号改为小于号即可。
即： $dis_ u < dis_ v + w$ 。
这题的难点依旧在于建边。
看到题目，给出了五个约束条件。
我们先分析，粗略地列出下面的不等式组：
$\begin{cases}1\cdot A=B\ 2\cdot A <B\ 3\cdot A\geq B\ 4\cdot A >B\ 5\cdot A\leq B\end{cases}$
然后我们将其一个个转化为 $x_ i - x_ j \geq k$ 的形式。
小 $trick$：当出现 $>$ 或 $<$ 的情况，我们可以通过 $+1$ 或 $-1$ 来使符号变为 $\leq$ 或 $\geq$。
对于不等式 $1$：上文提过，转化为 $A-B\leq 0$ 和 $A-B \geq 0$ 。
对于不等式 $2$：可以用到上文的小 $trick$ ，先化为 $A+1\leq B$ 的形式，然后移项，再乘以 $-1$，可转化为 $B-A \geq 1$。
对于不等式 $3$：我们直接移项，化为 $A-B \geq 0$ 。
对于不等式 $4$：我们也可以用到上文中的小 $trick$，先化为$A\geq B+1$，然后移项，变为 $A-B \geq 1$。
对于不等式 $5$：先移项化为 $A-B\leq 0$ ，然后乘以 $-1$，化为 $B-A \geq 0$。
这样，我们的 $5$ 个约束条件就转换完成了。
我们就可以按照上文说过的建图方式建图。
由于题目要求是求至少要准备的糖果数，所以我们要将跑的最长路径的值加起来。
注意！ 我们要跑最长路径。
但是有个很奇怪的事情，也许是因为数据的特殊性，我用 $queue$ 死活会挂一个点，用 $stack$ 就可以过。
Code：
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<iostream>
#define R register
using namespace std;
typedef long long ll;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read() {
R char c=getchar();R int x=0;R bool f=0;
for(;!isdigit(c);c=getchar())f^ =!(c^ 45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c&15);
return f?(~x+1):x;
}
const int N = 150005;
struct DAG {
int nxt;
int to;
int w;
}G[N];
int n, m;
int outdeg[N], head[N], edge_ num = 0, dis[N];
bool vis[N];
inline void add_ edge (int x, int y, int z) {
G[++edge_ num].nxt = head[x];
G[edge_ num].to = y;
G[edge_ num].w = z;
head[x] = edge_ num;
}
bool tag = true;
inline void SPFA () {
stack<int> st;
st.push(0);
while (!st.empty()) {
int u = st.top();
outdeg[u] ++;
if (outdeg[u] == n + 1) {
//出现负环
printf("-1");
tag = false;
return ;
}
st.pop();
vis[u] = false;
for (R int i = head[u]; i; i = G[i].nxt) {
int v = G[i].to;
if (dis[v] < dis[u] + G[i].w) {
//三角形不等式
dis[v] = dis[u] + G[i].w;
if (vis[v] == false) {
vis[v] = true;
st.push (v);
}
}
}
}
}
int main() {
n = read(), m = read();
while (m--) {
int op = read(), u = read(), v = read();
if (op == 1) {
add_ edge (u, v, 0);
add_ edge (v, u, 0);
}
if (op == 2) {
if (u == v) {
puts ("-1");
return 0;
}
add_ edge (u, v, 1);
}
if (op == 3) {
add_ edge (v, u, 0);
}
if (op == 4) {
if (u == v) {
puts ("-1");
return 0;
}
add_ edge (v, u, 1);
}
if (op == 5) {
add_ edge (u, v, 0);
}
}
for (int i = 1; i <= n; i ++) {
add_ edge (0, i, 1);
//与超级源点0连边
}
vis[0] = true;
SPFA ();
if (tag == false) {
return 0;
}
ll sum = 0;
for (int i = 1; i <= n; i ++) {
sum += dis[i];
}
printf ("%lld", sum);
return 0;
}
仔细阅读题目，我们就能发现，题目又给出了 $m$ 个 $T_ i - T_ j \leq b$ 的不等式。
这样我们按照差分约束的基本套路，建一条 $j->i$ 边权为 $b$ 的边即可。
但是题目要求每个任务的起始时间，按照题意，我们知道，我们跑完单源最短路径后，最小的 $dis$ 就是该工程的最早开始时间。
于是，我们最后需要找到最小的 $dis$ ，最后输出每一个 $dis$ 与最小的 $dis$ 的差值。
Code：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 15555;
const int inf = 0x3f3f3f3f;
struct EDGE {
int to;
int nxt;
int w;
}e[N<<1];
int edge_ num = 0, head[N];
inline void add_ edge (int x, int y, int z) {
e[++edge_ num].nxt = head[x];
e[edge_ num].to = y;
e[edge_ num].w = z;
head[x] = edge_ num;
}
int dis[N], num[N], n, m;
bool inque[N], tag = false;
//inque标记是否在队中
//tag标记是否有负环
inline void SPFA(int x) {
queue<int> q;
memset (dis, inf, sizeof (dis));//边权最初最大化
q.push (x);//入队
num[x] ++;//入队次数加一
dis[x] = 0;//源点与源点的最短路径长度为0
inque[x] = true;//标记在队中
while (!q.empty()) {//队列非空循环
int u = q.front();//取队头
q.pop();//弹出队头
inque[u] = false;//标记不在队中
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] > dis[u] + e[i].w) {//三角形不等式
dis[v] = dis[u] + e[i].w;//更新边权
if (inque[v] == false) {//未入队标记
q.push (v);//入队
inque[v] = true;//标记入队
num[v] ++; //入队次数加一
if (num[v] >= n + 1) {//入队次数超过点数，则出现负环
tag = true;//标记出现负环
return ;//退出循环
}
}
}
}
}
return ;
}
int main() {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= m; i ++) {
int x, y, z;
scanf ("%d%d%d", &x, &y, &z);
add_ edge (y, x, z);
//tx-ty≤z 所以建一条y->x 边权为z的边
}
for (int i = 1; i <= n; i ++) {
add_ edge (0, i, 0);
//与超级源点0建一条边权为0的边
}
SPFA (0);//从超级源点0开始跑单源最短路径
if (tag == true) {
puts ("NO SOLUTION");
//出现负环无解
return 0;
}
int min_ dis = inf;
for (int i = 1; i <= n; i ++) {
min_ dis = min (min_ dis, dis[i]);
//寻找最小的dis
}
for (int i = 1; i <= n; i ++) {
printf ("%d\n", dis[i] - min_ dis);
//输出每个dis与最小dis的差值
}
return 0;
}
题目给出了两个条件：
$I$： 第 $b$ 次挤奶在第 $a$ 次挤奶结束至少 $x$ 天后进行。
$II$：第 $i$ 次挤奶不早于第 $S_ i$ 天。
这样，我们就能转化出两个不等式：
$b-a\geq x$
和
$i\geq S_ i$ ，我们也可以将其化为 $i - 0 \geq S_ i$ 。
于是，我们就拥有了两个约束条件。
建两种边：
$1.$ 建 $a->b$ 边权为 $x$ 的边。
$2.$ 建 $0->i$ 边权为 $S_ i$ 的边。
因为约束条件是 $\geq$ 形式的，所以跑单源最长路径。
Code：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 3e5 + 7;
const int inf = 0x3f3f3f3f;
struct EDGE {
int nxt;
int to;
int w;
}e[N];
int head[N], edge_ num = 0, n, m, c;
inline void add_ edge (int x, int y, int z) {
e[++edge_ num].nxt = head[x];
e[edge_ num].to = y;
e[edge_ num].w = z;
head[x] = edge_ num;
}
ll dis[N];
bool inque[N];
inline void SPFA (int s) {
queue<int> q;
memset (dis, -inf ,sizeof (dis));//最长路，边权初始为负无穷
dis[s] = 0;//源点与源点的最短路径长度为0
q.push(s); //源点入队
inque[s] = true;//标记入队
while (!q.empty()) {
int u = q.front();//取出队头
q.pop();//弹出队头
inque[u] = false;//标记不在队中
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] < dis[u] + e[i].w) {//三角形不等式
dis[v] = dis[u] + e[i].w;//更新
if (inque[v] == false) {//不在队中时
q.push (v);//入队
inque[v] = true;//标记入队
}
}
}
}
}
int main() {
scanf ("%d%d%d", &n, &m, &c);
for (int i = 1; i <= n; i ++) {
int t;
scanf ("%d", &t);
add_ edge(0, i, t);//超级源点连边
}
for (int i = 1; i <= c; i ++) {
int x, y, z;
scanf ("%d%d%d", &x, &y, &z);
add_ edge (x, y, z);
}
SPFA(0);//从超级源点开始跑单源最长路径
for (int i = 1; i <= n; i ++) {
printf ("%lld\n", dis[i]);
}
return 0;
}
