简介

给定差分不等式组

$$\{\begin{array}{l}{X}_1-X_2\le 1\\ X_3-X_2\le 3\\ X_4-X_1\le -2\\ \cdots \end{array}$$

求一组满足所有条件的 $X_1\cdots X_n$ 的解。

以上形式的不等式组称作「差分约束系统」。

原理

根据 松弛操作 原理，当 SPFA 结束时，图中任意两个节点 $i,j$ 满足

$$\text{dis}[j]\le \text{dis}[i]+g[i,j]$$

事实上，差分约束系统的不等式可以变形为

$$X_j\le X_i+C$$

于是令 $\text{dis}[j]=X_j,\text{dis}[i]=X_i,g[i,j]=C$。

在图上跑一遍 SPFA 后，$X_1\cdots X_n$ 便满足差分不等式组。

模板

bool in[], X[]; // 将 dis[] 换成 X[]，便于理解
struct node {
    int val, len;
};
vector<int> g[];

void add(int X_j, X_i, C) { // X_j - X_i ≤ C
    g[X_i].push_back(node{X_j, C});
}

void spfa(int s) {
    memset(in, false, sizeof in);
    memset(X, 0x7f, sizeof X);
    X[s] = 0;
    queue<int> Q;
    Q.push(s), in[s] = true;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop(), in[u] = false;
        for (int i = 0; i < (int) g[u].size(); i ++) {
            int v = g[u][i].val;
            int d = g[u][i].len;
            if (X[v] > X[u] + d) {
                X[v] = X[u] + d;
                if (!in[v]) {
                    Q.push(v), in[v] = true;
                }
            }
        }
    }
}