差分约束
差分约束系统 是一种特殊的
差分约束系统中的每个约束条件
注意到,如果
设
一般使用 Bellman-Ford 或队列优化的 Bellman-Ford(俗称 SPFA,在某些随机图跑得很快)判断图中是否存在负环,最坏时间复杂度为
常用变形技巧¶
例题 luogu P1993 小 K 的农场¶
题目大意:求解差分约束系统,有
题意 | 转化 | 连边 |
---|---|---|
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 | #include <algorithm>
#include <cstdio>
#include <cstring>
#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;
inline 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() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int op, x, y, z;
scanf("%d", &op);
if (op == 1) {
scanf("%d%d%d", &x, &y, &z);
addedge(y, x, z);
} else if (op == 2) {
scanf("%d%d%d", &x, &y, &z);
addedge(x, y, -z);
} else {
scanf("%d%d", &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) {
puts("No");
return 0;
}
}
}
}
puts("Yes");
return 0;
}
|
例题 P4926[1007]倍杀测量者¶
不考虑二分等其他的东西,这里只论述差分系统
对每个
Bellman-Ford 判负环代码实现¶
下面是用 Bellman-Ford 算法判断图中是否存在负环的代码实现,请在调用前先保证图是连通的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | // C++ Version
bool Bellman_Ford() {
for (int i = 0; i < n; i++) {
bool jud = false;
for (int j = 1; j <= n; j++)
for (int k = h[j]; ~k; k = nxt[k])
if (dist[j] > dist[p[k]] + w[k])
dist[j] = dist[p[k]] + w[k], jud = true;
if (!jud) break;
}
for (int i = 1; i <= n; i++)
for (int j = h[i]; ~j; j = nxt[j])
if (dist[i] > dist[p[j]] + w[j]) return false;
return true;
}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | # Python Version
def Bellman_Ford():
for i in range(0, n):
jud = False
for j in range(1, n + 1):
while ~k:
k = h[j]
if dist[j] > dist[p[k]] + w[k]:
dist[j] = dist[p[k]] + w[k]; jud = True
k = nxt[k]
if jud == False:
break
for i in range(1, n + 1):
while ~j:
j = h[i]
if dist[i] > dist[p[j]] + w[j]:
return False
j = nxt[j]
return True
|
习题¶
POJ 2983 Is the Information Reliable?
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:Ir1d, Anguei, hsfzLZH1
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用