跳转至

差分約束

定義

差分約束系統 是一種特殊的 \(n\) 元一次不等式組，它包含 \(n\) 個變量 \(x_1,x_2,\dots,x_n\) 以及 \(m\) 個約束條件，每個約束條件是由兩個其中的變量做差構成的，形如 \(x_i-x_j\leq c_k\)，其中 \(1 \leq i, j \leq n, i \neq j, 1 \leq k \leq m\) 並且 \(c_k\) 是常數（可以是非負數，也可以是負數）。我們要解決的問題是：求一組解 \(x_1=a_1,x_2=a_2,\dots,x_n=a_n\)，使得所有的約束條件得到滿足，否則判斷出無解。

差分約束系統中的每個約束條件 \(x_i-x_j\leq c_k\) 都可以變形成 \(x_i\leq x_j+c_k\)，這與單源最短路中的三角形不等式 \(dist[y]\leq dist[x]+z\) 非常相似。因此，我們可以把每個變量 \(x_i\) 看做圖中的一個結點，對於每個約束條件 \(x_i-x_j\leq c_k\)，從結點 \(j\) 向結點 \(i\) 連一條長度為 \(c_k\) 的有向邊。

注意到，如果 \(\{a_1,a_2,\dots,a_n\}\) 是該差分約束系統的一組解，那麼對於任意的常數 \(d\)，\(\{a_1+d,a_2+d,\dots,a_n+d\}\) 顯然也是該差分約束系統的一組解，因為這樣做差後 \(d\) 剛好被消掉。

過程

設 \(dist[0]=0\) 並向每一個點連一條權重為 \(0\) 邊，跑單源最短路，若圖中存在負環，則給定的差分約束系統無解，否則，\(x_i=dist[i]\) 為該差分約束系統的一組解。

性質

一般使用 Bellman–Ford 或隊列優化的 Bellman–Ford（俗稱 SPFA，在某些隨機圖跑得很快）判斷圖中是否存在負環，最壞時間複雜度為 \(O(nm)\)。

常用變形技巧

例題 luogu P1993 小 K 的農場

題目大意：求解差分約束系統，有 \(m\) 條約束條件，每條都為形如 \(x_a-x_b\geq c_k\)，\(x_a-x_b\leq c_k\) 或 \(x_a=x_b\) 的形式，判斷該差分約束系統有沒有解。

題意 轉化 連邊
\(x_a - x_b \geq c\) \(x_b - x_a \leq -c\) add(a, b, -c);
\(x_a - x_b \leq c\) \(x_a - x_b \leq c\) add(b, a, c);
\(x_a = x_b\) \(x_a - x_b \leq 0, \space x_b - x_a \leq 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 <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;

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] 倍殺測量者

不考慮二分等其他的東西，這裏只論述差分系統 \(\frac{x_i}{x_j}\leq c_k\) 的求解方法。

對每個 \(x_i,x_j\) 和 \(c_k\) 取一個 \(\log\) 就可以把乘法變成加法運算，即 \(\log x_i-\log x_j \leq \log c_k\)，這樣就可以用差分約束解決了。

Bellman–Ford 判負環代碼實現

下面是用 Bellman–Ford 算法判斷圖中是否存在負環的代碼實現，請在調用前先保證圖是連通的。

實現 
 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
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?

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, Anguei, hsfzLZH1
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用