差分约束

差分约束系统 是一种特殊的 元一次不等式组，它包含 个变量 以及 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 ，其中 并且 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 ，使得所有的约束条件得到满足，否则判断出无解。

差分约束系统中的每个约束条件 都可以变形成 ，这与单源最短路中的三角形不等式 非常相似。因此，我们可以把每个变量 看做图中的一个结点，对于每个约束条件 ，从结点 向结点 连一条长度为 的有向边。

注意到，如果 是该差分约束系统的一组解，那么对于任意的常数 ， 显然也是该差分约束系统的一组解，因为这样做差后 刚好被消掉。

设 并向每一个点连一条权重为 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则， 为该差分约束系统的一组解。

一般使用 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
62
63
64
65
  #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

习题

Usaco2006 Dec Wormholes 虫洞

「SCOI2011」糖果

POJ 1364 King

POJ 2983 Is the Information Reliable?

build本页面最近更新：2021/10/11 17:06:03，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：Anguei, hsfzLZH1, Ir1d, Chrogeek, Enter-tainer, H-Shen, Henry-ZHR, iamtwz, kenlig, ouuan, StudyingFather, Xeonacid
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论