差分约束系统

简介 #

给定差分不等式组

$$\begin{cases} X_1 - X_2 ≤ 1\\ X_3 - X_2 ≤ 3\\ X_4 - X_1 ≤ -2\\ \cdots \end{cases}$$

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

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

原理 #

根据松弛操作原理，当 SPFA 程序结束时，图中任意两个节点 $i,j$ 满足 $\dis[j] ≤ \dis[i] + g[i,j]$.

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

$$X_j ≤ X_i + C$$

于是令 $\dis[j]=X_j,\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;
                }
            }
        }
    }
}