【图论】差分约束系统

给定一组不等式：
\(x_{v1}-x_{u1}\le w_1\)
\(x_{v2}-x_{u2}\le w_2\)

（注意上面的变量的位置是(v,u,w)而不是(u,v,w)）

求满足上面约束的一组可行解，变形为 \(dis[v_1]\le dis[u_1]+w_1\) ，故从点 u 连接一条权值为 w_1 的边到点 v。

namespace SDC {

    const int MAXN = 2e5 + 10;

    int n;
    vector<pil> G[MAXN];

    ll dis[MAXN];
    int cnt[MAXN];
    bool vis[MAXN];

    queue<int> Q;

    bool bellmanford() {
        fill(dis + 1, dis + 1 + n, LINF);
        fill(cnt + 1, cnt + 1 + n, 0);
        fill(vis + 1, vis + 1 + n, 0);
        while(!Q.empty())
            Q.pop();
        dis[n] = 0;
        vis[n] = 1;
        Q.push(n);
        while(!Q.empty()) {
            int u = Q.front();
            Q.pop();
            vis[u] = 0;
            ++cnt[u];
            if(cnt[u] == n)
                return false;
            for(pil &p : G[u]) {
                int v = p.first;
                ll w = p.second;
                if(dis[v] <= dis[u] + w)
                    continue;
                dis[v] = dis[u] + w;
                if(!vis[v]) {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
        }
        return true;
    }

    bool sdc() {
        ++n;
        G[n].clear();
        for(int i = 1; i <= n - 1; ++i)
            G[n].eb(i, 0);
        int res = bellmanford();
        G[n].clear();
        --n;
        return res;
    }

}

其他：

求一组非负整数解：全部加上一个最小值

上面要求是两个变量的差分满足某个不等式的约束。可以通过前缀和和差分的转化把区间求和转化为前缀和的差分。令 \(S_i=a_1+a_2+\cdots+a_i\) ，那么某个区间[L,R]的元素的和不超过一个定值w转换为 \(S_R-S_{L-1}\le w\) 。

对于两个变量的比例满足某个不等式的约束，那么可以通过取对数变成差分约束。

若w全部都>=0，可以用Dijkstra求解。