Skip to content

Difference Constraints

Definition

Difference constraints is a special kind of \(n\)-variable system of linear inequalities. It consists of \(n\) variables \(x_1,x_2,\dots,x_n\) and \(m\) constraints, each of which is formed by the difference of two variables, in the form \(x_i-x_j\leq c_k\), where \(1 \leq i, j \leq n, i \neq j, 1 \leq k \leq m\) and \(c_k\) is a constant (which can be non-negative or negative). The problem is to find a solution \(x_1=a_1,x_2=a_2,\dots,x_n=a_n\) that satisfies all constraints, or determine that no solution exists.

Each constraint \(x_i-x_j\leq c_k\) in a difference constraints system can be transformed into \(x_i\leq x_j+c_k\), which closely resembles the triangle inequality \(dist[y]\leq dist[x]+z\) in single-source shortest paths. Therefore, we can treat each variable \(x_i\) as a node in a graph. For each constraint \(x_i-x_j\leq c_k\), we add a directed edge from node \(j\) to node \(i\) with length \(c_k\).

Note that if \(\{a_1,a_2,\dots,a_n\}\) is a solution to the difference constraints system, then for any constant \(d\), \(\{a_1+d,a_2+d,\dots,a_n+d\}\) is also a solution, because the \(d\) cancels out when taking differences.

Process

Set \(dist[0]=0\) and add an edge of weight \(0\) from node \(0\) to every other node. Run a single-source shortest path algorithm. If a negative cycle exists in the graph, then the given difference constraints system has no solution. Otherwise, \(x_i=dist[i]\) is a solution to the system.

Properties

Typically, Bellman–Ford or its queue-optimized version (commonly known as SPFA, which runs fast on some random graphs) is used to detect negative cycles. The worst-case time complexity is \(O(nm)\).

Common Transformation Techniques

Example Problem luogu P1993 Little K's Farm

Problem summary: Solve a difference constraints system with \(m\) constraints, each of the form \(x_a-x_b\geq c_k\), \(x_a-x_b\leq c_k\), or \(x_a=x_b\). Determine whether the system has a solution.

Constraint Transformation Add Edge
\(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);

Run negative cycle detection. If no negative cycle exists, output Yes; otherwise, output No.

Reference Code 
 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) {  // Add edge
  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()) {  // Detect negative cycle, see above
    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;
}

Example Problem P4926[1007]倍杀测量者

Ignoring other aspects like binary search, here we only discuss solving the difference system \(\frac{x_i}{x_j}\leq c_k\).

Taking the logarithm of each \(x_i\), \(x_j\), and \(c_k\) transforms multiplication into addition: \(\log x_i-\log x_j \leq \log c_k\). This allows the problem to be solved using difference constraints.

Bellman–Ford Negative Cycle Detection Implementation

Below is the code implementation for detecting negative cycles in a graph using the Bellman–Ford algorithm. Ensure the graph is connected before calling.

Implementation 
 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

Exercises

Usaco2006 Dec Wormholes

「SCOI2011」Candy

POJ 1364 King

POJ 2983 Is the Information Reliable?

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