差分约束系统
差分约束系统是将不等式组的问题转化为图论问题。
前置知识
例题
思路
我们将 \(x_u - x_v \le y_u\) 换为 \(x_u \le x_v + y_u\)。
然后我们建立一条连接 \(v, u\)（注意是 \(v, u\) 不是 \(u, v\)）权值为 \(y_u\) 的边。
我们发现从根节点到节点 \(u\) 的最短路径长度 \(dis_u\) 就是对 \(x_u\) 上限的限制。
比如这个图：
实际上这个图描述的就是关系：
\[\begin{aligned} x_2 - x_1 \le 1\\ x_3 - x_2 \le 2\\ x_1 - x_3 \le 5 \end{aligned} \]我们以 \(1\) 为源点的最短路为
\[\begin{aligned} dis_1 = 0\\ dis_2 = 1\\ dis_3 = 3 \end{aligned} \]那么就有
\[\begin{aligned} x_2 \le x_1 + dis_2\\ x_3 \le x_1 + dis_3 \end{aligned} \]即
\[\begin{aligned} x_2 \le x_1 + 1\\ x_3 \le x_1 + 3 \end{aligned} \]如果有负环，那么从 \(1\) 号点走，回到 \(1\) 号点，就会出现 \(x_1 \le x_1 + w, w < 0\) 的场面，显然是矛盾的，所以如果出现负环，那么无解。
怎么用 SPFA 判断负环：参见我的博客。
然后为了使图联通，我们建立一个超级源点 \(S\) 连向每一个点且权值为 \(0\) 的边。
代码
/*******************************
| Author: SunnyYuan
| Problem: P5960 【模板】差分约束算法
| Contest: Luogu
| URL: https://www.luogu.com.cn/problem/P5960
| When: 2023-09-18 09:13:00
|
| Memory: 128 MB
| Time: 1000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
const int N = 5010, M = 10010;
struct edge {
int to, next, w;
} e[M];
int head[N], idx;
void add(int u, int v, int w) {
idx++, e[idx].to = v, e[idx].next = head[u], e[idx].w = w, head[u] = idx;
}
int n, m;
int dis[N];
int cnt[N];
bool st[N];
bool spfa(int u) {
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
queue<int> q;
q.push(u);
st[u] = true;
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = head[t]; i; i = e[i].next) {
int to = e[i].to;
if (dis[to] > dis[t] + e[i].w) {
dis[to] = dis[t] + e[i].w;
cnt[to] = cnt[t] + 1;
if (cnt[to] >= n + 1) return false;
if (!st[to]) {
st[to] = true;
q.push(to);
}
}
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
int u, v, w;
for (int i = 1; i <= n; i++) add(0, i, 0);
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
// Xu - Xv <= w
// Xu <= Xv + w
add(v, u, w);
}
if (spfa(0)) for (int i = 1; i <= n; i++) cout << dis[i] << ' ';
else cout << "NO\n";
return 0;
}
例题
My Blog:P7515 [省选联考 2021 A 卷] 矩阵游戏题解
标签：图论,le,idx,int,差分,aligned,模板,dis From： https://www.cnblogs.com/Yuan-Jiawei/p/18315364