差分约束系统简介¶
算法介绍¶
算法思想¶
差分约束系统是一种特殊的多元一次不等式组，他有 \(n\) 个变量以及 \(m\) 条约束条件，每一个约束条都形如 \(x_i-x_j\le k\)，其中 \(i\) 和 \(j\) 都是 \(0\sim n\) 的整数，而 \(k\) 必须是常数，可正可负。我们需要解决这个差分约束系统是否有解，也就是是否满一组 \((x_1,x_2,\dots,x_n)\) 的解能够满足所有 \(m\) 条约束条件。
根据不等式的性质，每一个约束条件都可以更改为 \(x_i\le x_j+k\)，而我们可以发现最短路的求解当中正好有一个三角形不等式和它几乎一模一样。因此，我们就可以将每一个变量 \(x_i\) 看做图中的一个结点，将每一个约束条件看为图中的一条边。每一个约束条件 \(x_i-x_j\le k\to x_i\le x_j+k\) 可以看做从结点 \(j\) 向结点 \(i\) 连了一条权值为 \(k\) 的有向边。
继续根据不等式的性质，假设有一个常数 \(a\)，那么若 \((x_1,x_2,\dots,x_n)\) 是一组解的话，\((x_1+d,x_2+d,\dots,x_n+d)\) 也将会是此差分约束系统的一组解。
实现¶
首先我们可以知道，跑最短路的时候若该组差分约束系统没有可行解，那么就会跑出正环，因此我们可以使用 Bellman-Ford 对负边权图跑最短路径算法并判断是否有正环。但是这个图可能不一定是连通的，因此我们需要建立一个超级源点 \(0\)，然后往每一个结点都脸上一条边权位 \(0\) 的边，并从超级源点开始跑最长路，若遇到了负环就说明无解。
可以使用 Bellman-Ford 的队列优化版本 SPFA，在随机图内可以拥有 \(\mathcal O(n+m)\) 的时间复杂度，但若有负环则和 Bellman-Ford 一样，是最坏 \(\mathcal O(nm)\) 的时间复杂度。
例题¶
P1993 小 K 的农场
小 K 在 MC 里面建立很多很多的农场，总共 \(n\) 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 \(m\) 个），以下列三种形式描述：
- 农场 \(a\) 比农场 \(b\) 至少多种植了 \(c\) 个单位的作物；
- 农场 \(a\) 比农场 \(b\) 至多多种植了 \(c\) 个单位的作物；
- 农场 \(a\) 与农场 \(b\) 种植的作物数一样多。
但是，由于小 K 的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
这是一道非常裸的模板题，如果你已经仔细看懂了前面的简介的话，那么写出这道题的代码肯定不在话下。
代码
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
ll n, m;
queue<ll> q;
int main() {
cin >> n >> m;
vector<vector<pair<ll, ll>>> e(n + 1, vector<pair<ll, ll>>());
for (ll i = 1, o, u, v, w; i <= m; i++) {
cin >> o >> u >> v;
if (o == 1) {
cin >> w, e[v].emplace_back(u, w);
} else if (o == 2) {
cin >> w, e[u].emplace_back(v, -w);
} else {
e[u].emplace_back(v, 0);
e[v].emplace_back(u, 0);
}
}
for (ll i = 1; i <= n; i++) {
e[0].emplace_back(i, 0);
}
vector<ll> d(n + 1, -1e9), f(n + 1), c(n + 1);
for (q.push(0), d[0] = 0, f[0] = 1; q.size(); q.pop()) {
ll t = q.front();
f[t] = 0;
for (auto i : e[t]) {
if (d[t] + i.second > d[i.first]) {
d[i.first] = d[t] + i.second;
if (!f[i.first]) {
f[i.first] = 1;
q.push(i.first);
if (++c[i.first] >= n) {
cout << "No\n";
return 0;
}
}
}
}
}
cout << "Yes\n";
return 0;
}