差分约束

问题描述

给定不等式组 $\{x_{u_i}-x_{v_i}\le a_i\}_{i=1}^m$，求一组解或给定 $u, v$ 求有解的情况下 $\max\{x_u-x_v\}$ 。

做法

把 $x_1,..,x_n$ 看成有向图中的 $n$ 个点，对于一个不等式 $x_u-x_v\le a$，连一条 $v\to u$ 的，边权为 $a$ 的边。

求一组解

超级源点向所有点连 $0$ 边，以超级源为起点跑 Bellman-Ford 最短路。若有负环，则说明不等式存在冲突。若没有负环，则根据 Bellman-Ford 求出的最短路 $dis$ 数组，得到的就是一组解。

超级源连的 $0$ 边相当于其他点的值都小于等于 $0$，但是这并不影响最后得到的答案。如果最后有答案，一定都是有限的解，而 $\{x_i\}$ 是一组解，则 $\{x_i+d\}$ 也是一组解，因此如果原问题有解，一定存在所有数都小于等于 $0$ 的解。

求两个未知数相减的最大值/最小值

注意到，如果一个差分约束图中，有解，且以 $u$ 点为起点跑 Bellman-Ford，则最后得到的 $dis[v]=\max\{x_v-x_u\}$。

证明：

因为有解，根据最短路定理此时的 $dis[..]$ 是可以作为一组解的。只需要证明不能找到比 $dis[v]$ 更大的解即可，假设有更大的解 $dis[v]+\delta$，考虑找到的一条最短的路径是 $u\to b_1\to ...\to v$，那么这里面一定存在 $b_i,b_{i+1}$ 使得 $dis[b_{i+1}]-dis[b_i]>a$，这与 $x_{b_{i+1}}-x_{b_i}\le a$ 矛盾。

怎么求最小值？$\min\{x_v-x_u\}=-\max\{x_u-x_v\}$

点击查看代码

struct ConstraintSystem {
    using ll = long long;
    vector<vector<pair<int, int>>> adj;
    int _n;

    ConstraintSystem(int n): _n(n), adj(n + 1) {
        for(int i = 1; i <= n; i++) {
            adj[0].emplace_back(i, 0);
        }
    }

    void leq_than(int u, int v, int w) { // xu - xv <= w
        adj[v].emplace_back(u, w);
    }

    void geq_than(int u, int v, int w) { // xu - xv >= w
        adj[u].emplace_back(v, -w);
    }

    void less_than(int u, int v, int w) { // xu - xv < w
        leq_than(u, v, w - 1);
    }

    void greater_than(int u, int v, int w) { // xu - xv > w
        geq_than(u, v, w + 1);
    }

    void eq(int u, int v, int w) {
        leq_than(u, v, w);
        geq_than(u, v, w);
    }

    // get all result: solve(0, dis);
    // get max{x_u - x_v}: solve(v, dis); ans = dis[u];
    // get min{x_u - x_v} = -max{x_v - x_u}: solve(u, dis); ans = -dis[v]; 
    int solve(int start, vector<ll> &dis) {
        queue<int> q;
        dis.resize(_n + 1);
        fill(dis.begin(), dis.end(), (ll) 1e18);
        dis[start] = 0;
        q.push(start);
        vector<int> inq(_n + 1), tot(_n + 1);
        inq[start] = 1;
        while(q.size()) {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            tot[u]++;
            if(tot[u] > _n) {
                return 0;
            }
            for(auto [v, w] : adj[u]) {
                if(dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    if(!inq[v]) {
                        inq[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
        return 1;
    }
};