跳转至

# 差分约束

## 定义

差分约束系统 是一种特殊的 𝑛 n 元一次不等式组，它包含 𝑛 n 个变量 𝑥 1,𝑥 2,…,𝑥 𝑛 x 1,x 2,…,x n 以及 𝑚 m 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 𝑥 𝑖 −𝑥 𝑗 ≤𝑐 𝑘 x i−x j≤c k，其中 1 ≤𝑖,𝑗 ≤𝑛,𝑖 ≠𝑗,1 ≤𝑘 ≤𝑚 1≤i,j≤n,i≠j,1≤k≤m 并且 𝑐 𝑘 c k 是常数（可以是非负数，也可以是负数）．我们要解决的问题是：求一组解 𝑥 1 =𝑎 1,𝑥 2 =𝑎 2,…,𝑥 𝑛 =𝑎 𝑛 x 1=a 1,x 2=a 2,…,x n=a n，使得所有的约束条件得到满足，否则判断出无解．

差分约束系统中的每个约束条件 𝑥 𝑖 −𝑥 𝑗 ≤𝑐 𝑘 x i−x j≤c k 都可以变形成 𝑥 𝑖 ≤𝑥 𝑗 +𝑐 𝑘 x i≤x j+c k，这与单源最短路中的三角形不等式 𝑑 𝑖 𝑠 𝑡[𝑦] ≤𝑑 𝑖 𝑠 𝑡[𝑥] +𝑧 d i s t[y]≤d i s t[x]+z 非常相似．因此，我们可以把每个变量 𝑥 𝑖 x i 看做图中的一个结点，对于每个约束条件 𝑥 𝑖 −𝑥 𝑗 ≤𝑐 𝑘 x i−x j≤c k，从结点 𝑗 j 向结点 𝑖 i 连一条长度为 𝑐 𝑘 c k 的有向边．

注意到，如果 {𝑎 1,𝑎 2,…,𝑎 𝑛}{a 1,a 2,…,a n} 是该差分约束系统的一组解，那么对于任意的常数 𝑑 d，{𝑎 1 +𝑑,𝑎 2 +𝑑,…,𝑎 𝑛 +𝑑}{a 1+d,a 2+d,…,a n+d} 显然也是该差分约束系统的一组解，因为这样做差后 𝑑 d 刚好被消掉．

## 过程

设 𝑑 𝑖 𝑠 𝑡[0] =0 d i s t[0]=0 并向每一个点连一条权重为 0 0 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，𝑥 𝑖 =𝑑 𝑖 𝑠 𝑡[𝑖]x i=d i s t[i] 为该差分约束系统的一组解．

## 性质

一般使用 Bellman–Ford 或队列优化的 Bellman–Ford（俗称 SPFA，在某些随机图跑得很快）判断图中是否存在负环，最坏时间复杂度为 𝑂(𝑛 𝑚)O(n m)．

## 常用变形技巧

### 例题 luogu P1993 小 K 的农场

题目大意：求解差分约束系统，有 𝑚 m 条约束条件，每条都为形如 𝑥 𝑎 −𝑥 𝑏 ≥𝑐 𝑘 x a−x b≥c k，𝑥 𝑎 −𝑥 𝑏 ≤𝑐 𝑘 x a−x b≤c k 或 𝑥 𝑎 =𝑥 𝑏 x a=x b 的形式，判断该差分约束系统有没有解．

题意 | 转化 | 连边
--- | --- | ---
𝑥 𝑎 −𝑥 𝑏 ≥𝑐 x a−x b≥c | 𝑥 𝑏 −𝑥 𝑎 ≤ −𝑐 x b−x a≤−c | `add(a, b, -c);`
𝑥 𝑎 −𝑥 𝑏 ≤𝑐 x a−x b≤c | 𝑥 𝑎 −𝑥 𝑏 ≤𝑐 x a−x b≤c | `add(b, a, c);`
𝑥 𝑎 =𝑥 𝑏 x a=x b | 𝑥 𝑎 −𝑥 𝑏 ≤0, 𝑥 𝑏 −𝑥 𝑎 ≤0 x a−x b≤0, x b−x a≤0 | `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;
    }

### 例题 P4926[1007] 倍杀测量者

不考虑二分等其他的东西，这里只论述差分系统 𝑥 𝑖 𝑥 𝑗 ≤𝑐 𝑘 x i x j≤c k 的求解方法．

对每个 𝑥 𝑖,𝑥 𝑗 x i,x j 和 𝑐 𝑘 c k 取一个 l o g log 就可以把乘法变成加法运算，即 l o g⁡𝑥 𝑖 −l o g⁡𝑥 𝑗 ≤l o g⁡𝑐 𝑘 log⁡x i−log⁡x j≤log⁡c k，这样就可以用差分约束解决了．

## Bellman–Ford 判负环代码实现

下面是用 Bellman–Ford 算法判断图中是否存在负环的代码实现，请在调用前先保证图是连通的．

实现
C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    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
    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?

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, Anguei, hsfzLZH1, StudyingFather, Enter-tainer, Henry-ZHR, iamtwz, Menci, Tiphereth-A, Xeonacid, Chrogeek, Haohu Shen, ImpleLee, kenlig, ksyx, ouuan, shawlleyw
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用