Bỏ qua

Ràng buộc sai phân

Định nghĩa

Hệ ràng buộc hiệu (hay "hệ chênh lệch ràng buộc") là một hệ bất phương trình tuyến tính đặc biệt gồm \(n\) biến \(x_1,x_2,\dots,x_n\) và \(m\) điều kiện ràng buộc, mỗi điều kiện đều là hiệu của hai biến, có dạng \(x_i-x_j\leq c_k\), với \(1 \leq i, j \leq n, i \neq j, 1 \leq k \leq m\) và \(c_k\) là hằng số (có thể âm hoặc dương). Bài toán đặt ra là: tìm một bộ giá trị \(x_1=a_1,x_2=a_2,\dots,x_n=a_n\) sao cho mọi ràng buộc đều được thỏa mãn, hoặc kết luận là vô nghiệm.

Mỗi ràng buộc \(x_i-x_j\leq c_k\) có thể biến đổi thành \(x_i\leq x_j+c_k\), rất giống với bất đẳng thức tam giác trong bài toán đường đi ngắn nhất đơn nguồn: \(dist[y]\leq dist[x]+z\). Do đó, ta có thể coi mỗi biến \(x_i\) là một đỉnh trong đồ thị, với mỗi ràng buộc \(x_i-x_j\leq c_k\) thì nối một cạnh có hướng từ đỉnh \(j\) tới đỉnh \(i\) với trọng số \(c_k\).

Lưu ý rằng, nếu \(\{a_1,a_2,\dots,a_n\}\) là một nghiệm của hệ ràng buộc hiệu, thì với bất kỳ hằng số \(d\), bộ \(\{a_1+d,a_2+d,\dots,a_n+d\}\) cũng là một nghiệm, vì khi lấy hiệu thì \(d\) bị triệt tiêu.

Quy trình

Đặt \(dist[0]=0\) và nối từ đỉnh 0 tới mỗi đỉnh một cạnh trọng số 0, sau đó chạy thuật toán đường đi ngắn nhất đơn nguồn. Nếu đồ thị có chu trình âm, hệ ràng buộc hiệu vô nghiệm; ngược lại, \(x_i=dist[i]\) là một nghiệm của hệ.

Tính chất

Thường dùng Bellman–Ford hoặc Bellman–Ford tối ưu bằng hàng đợi (SPFA, chạy rất nhanh trên một số đồ thị ngẫu nhiên) để kiểm tra chu trình âm, độ phức tạp xấu nhất là \(O(nm)\).

Một số kỹ thuật biến đổi thường gặp

Ví dụ luogu P1993 Nông trại của K

Tóm tắt đề: Giải hệ ràng buộc hiệu với \(m\) điều kiện, mỗi điều kiện có dạng \(x_a-x_b\geq c_k\), \(x_a-x_b\leq c_k\) hoặc \(x_a=x_b\), kiểm tra hệ có nghiệm hay không.

Ý nghĩa đề Biến đổi Cách nối cạnh
\(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, x_b - x_a \leq 0\) add(b, a, 0), add(a, b, 0);

Chạy kiểm tra chu trình âm, nếu không có thì in Yes, ngược lại in No.

Tham khảo mã nguồn 
 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;
}

Ví dụ P4926[1007] Đo lường nhân bội

Không xét nhị phân hay các kỹ thuật khác, chỉ bàn về cách giải hệ \(\frac{x_i}{x_j}\leq c_k\) bằng ràng buộc hiệu.

Chỉ cần lấy \(\log\) cho mỗi \(x_i,x_j\) và \(c_k\), phép chia chuyển thành phép cộng: \(\log x_i-\log x_j \leq \log c_k\), khi đó có thể dùng hệ ràng buộc hiệu để giải.

Mã kiểm tra chu trình âm bằng Bellman–Ford

Dưới đây là mã kiểm tra chu trình âm bằng thuật toán Bellman–Ford. Khi dùng, cần đảm bảo đồ thị liên thông.

Cài đặt 
 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

Bài tập

Usaco2006 Dec Wormholes - Lỗ sâu

「SCOI2011」Kẹo

POJ 1364 King

POJ 2983 Thông tin có đáng tin cậy?

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:Ir1d, Anguei, hsfzLZH1
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply