差分约束
定义
差分约束系统 是一种特殊的 元一次不等式组,它包含 个变量 以及 个约束条件,每个约束条件是由两个其中的变量做差构成的,形如 ,其中 并且 是常数(可以是非负数,也可以是负数)。我们要解决的问题是:求一组解 ,使得所有的约束条件得到满足,否则判断出无解。
差分约束系统中的每个约束条件 都可以变形成 ,这与单源最短路中的三角形不等式 非常相似。因此,我们可以把每个变量 看做图中的一个结点,对于每个约束条件 ,从结点 向结点 连一条长度为 的有向边。
注意到,如果 是该差分约束系统的一组解,那么对于任意的常数 , 显然也是该差分约束系统的一组解,因为这样做差后 刚好被消掉。
过程
设 并向每一个点连一条权重为 边,跑单源最短路,若图中存在负环,则给定的差分约束系统无解,否则, 为该差分约束系统的一组解。
性质
一般使用 Bellman–Ford 或队列优化的 Bellman–Ford(俗称 SPFA,在某些随机图跑得很快)判断图中是否存在负环,最坏时间复杂度为 。
常用变形技巧
题目大意:求解差分约束系统,有 条约束条件,每条都为形如 , 或 的形式,判断该差分约束系统有没有解。
题意 | 转化 | 连边 |
---|
| | add(a, b, -c); |
| | add(b, a, c); |
| | add(b, a, 0), add(a, b, 0); |
跑判断负环,如果不存在负环,输出 Yes
,否则输出 No
。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65 | #include <cstring>
#include <iostream>
#include <queue>
using namespace std;
struct edge {
int v, w, next;
} e[40005];
int head[10005], vis[10005], tot[10005], cnt;
long long ans, dist[10005];
queue<int> q;
void addedge(int u, int v, int w) { // 加边
e[++cnt].v = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int op, x, y, z;
cin >> op;
if (op == 1) {
cin >> x >> y >> z;
addedge(y, x, z);
} else if (op == 2) {
cin >> x >> y >> z;
addedge(x, y, -z);
} else {
cin >> x >> y;
addedge(x, y, 0);
addedge(y, x, 0);
}
}
for (int i = 1; i <= n; i++) addedge(0, i, 0);
memset(dist, -0x3f, sizeof(dist));
dist[0] = 0;
vis[0] = 1;
q.push(0);
while (!q.empty()) { // 判负环,看上面的
int cur = q.front();
q.pop();
vis[cur] = 0;
for (int i = head[cur]; i; i = e[i].next)
if (dist[cur] + e[i].w > dist[e[i].v]) {
dist[e[i].v] = dist[cur] + e[i].w;
if (!vis[e[i].v]) {
vis[e[i].v] = 1;
q.push(e[i].v);
tot[e[i].v]++;
if (tot[e[i].v] >= n) {
cout << "No\n";
return 0;
}
}
}
}
cout << "Yes\n";
return 0;
}
|
不考虑二分等其他的东西,这里只论述差分系统 的求解方法。
对每个 和 取一个 就可以把乘法变成加法运算,即 ,这样就可以用差分约束解决了。
Bellman–Ford 判负环代码实现
下面是用 Bellman–Ford 算法判断图中是否存在负环的代码实现,请在调用前先保证图是连通的。
实现
习题
Usaco2006 Dec Wormholes 虫洞
「SCOI2011」糖果
POJ 1364 King
POJ 2983 Is the Information Reliable?
本页面最近更新:2024/5/8 20:33:33,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Anguei, hsfzLZH1, Ir1d, dkz051, Enter-tainer, Haohu Shen, Henry-ZHR, iamtwz, ImpleLee, kenlig, Menci, ouuan, shawlleyw, StudyingFather, Tiphereth-A, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用