1、问题类型描述
-
差分约束是一种特殊的 \(n\) 元一次不等式组，它包含 \(n\) 个变量 \(x_1,x_2,\cdots x_n\) 以及 \(m\) 个约束条件。
- 每个约束条件是由两个其中的变量做差构成的，形如 \(x_i-x_j \le c_k\)，其中 $ i \not= j, ; 1 \le k \le m ,; c_k \in R$
-
我们要解决的问题是求一组解:
- 使得所有的约束条件得到满足，否则判断出无解。
2、模型转换
-
变形一下：\(x_i \le x_j +c_k\)
- 容易发现，与最短路中的 \(dis[y] \le dis[x] + z\) 非常相似
-
如何理解？
-
我们就将不等式问题转换成为一个最短路径问题
-
我们可以把每个变量 \(x_i\) 看做图中的一个结点，对于每个约束条件 \(x_i-x_j \le c_k\)，看做从结点 \(j\) 向结点 \(i\) 连一条长度为 \(c_k\) 的有向边。
-
注意到，如果 \(\{ a_1,a_2,\cdots,a_n\}\) 是该差分约束系统的一组解，那么对于任意的常数 \(d\)，\(\{ a_1+d,a_2+d,\cdots,a_n+d\}\) 显然也是该差分约束系统的一组解，因为这样做差后 \(d\) 刚好被消掉。
-
3、不等式组无解
-
什么情况下，上面的多项式组无解？
-
在我们转换的模型中，如果一个点的最短距离 \(dis[i]\) 不存在，即负无穷大 → 存在负环
-
在原来的方程组里面，就是几个变量相互约束
-
所以就是利用 \(SPFA\) 判断负环的办法即可，即存在 \(num[i]>n\)
4、为什么不能用Dijkstra
\(Dijkstra\) 算法不能处理负数边权，已经确立 \(dis[i]\) 的点，若有负数边权，可能会被后续进来的点给更新掉。
故只能使用 \(Bellman-ford\) 算法和 \(SPFA\) 算法
5、拓展
-
题目给的形式为 \(x_i-x_j \le c_k\)
-
若为 \(x_i-x_j \ge c_k\)
- 则将两边同时乘以负号，有 \(x_j-x_i \le -c_k\)
-
若为 \(x_i-x_j = c_k\) ，即上面二者的统一
- \(x_i-x_j \le c_k\) 且 \(x_j-x_i \le -c_k\) ，建两条边即可
6、代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node{
int a,b;
};
int n, m;
vector<node> v[N];
int num[N], dis[N];
bool in[N];
int main() {
cin >> n >> m;
queue<int> q;
for (int i = 1; i <= m; i ++ ) {
int x, y, w;
cin >> y >> x >> w;
v[x].push_back({y, w});
}
for (int i = 1; i <= n; i++) {
v[0].push_back({i, 0});
}
memset(dis, 0x3f, sizeof dis);
dis[0] = 0;
q.push(0);
while (!q.empty()) {
int x = q.front();
q.pop();
num[x]++;
in[x] = false;
if (num[x] > n + 1) {
cout << "NO";
exit(0);
}
for (int i = 0; i < v[x].size(); i++) {
int u = v[x][i];
if (dis[u] > dis[x] + v[x][i].b) {
dis[u] = dis[x] + v[x][i].b;
if (!in[u]) {
in[u] = true;
q.push(u);
}
}
}
}
for (int i = 1; i <= n; i++) {
cout << dis[i] <<" ";
}
return 0;
}