差分约束简单入门

给您一连串的不等式组，让您找出满足该不等式的最大值或最小值。这就是差分约束要解决的问题。

引入

给出 $n$ 个变量和 $m$ 个不等式，就像这样

$$\begin{cases}x_1-x_2\le k_1\\x_3-x_2\le k_2\\x_3-x_1\le k_3\\x_4-x_2\le k_4\\x_3-x_2\le k_5\end{cases}$$

让您求出满足条件的 $x_1\dots x_4$ 中 $x_4-x_1$ 的最大值。

首先想到的就是手动推，很显然，计算机是不可能模拟手动推的。

与最短路算法的联系

考虑一下最短路算法的松弛过程。

if (dis[v] >= dis[u] + edge[i].val)
    dis[v] = dis[u] + edge[i].val;

这是不是很像上面的不等式？$k$ 就是边权，dis 数组就是那两个变量。但是符号是相反的。
这并不影响我们我们进行图论的建模。
我们只需要对于每个形如 $x_i-x_j\le k$ 的不等式，从 $j$ 到 $i$ 连边，边权即为 $k$ 。
这样跑一遍从 $1$ 到 $n$ 的最短路就是 $x_n-x_1$ 的最大值。

无解的情况

存在负环即无解。

在跑 SPFA 时记录一下每个点入队的次数，如果入队次数大于点数，即存在负环。

对于各种形式的不等式

• 求最小值：需要把每个不等式转化为 $x_i-x_j\ge k$ 的形式，从 $j$ 到 $i$ 连边，边权即为 $k$ 。然后跑一遍最长路即可。
• 求最大值：需要把每个不等式转化为 $x_i-x_j\le k$ 的形式，从 $j$ 到 $i$ 连边，边权即为 $k$ 。然后跑一遍最短路即可。
• 没有等号的情况：如果是 $x_i-x_j<k$ 的形式，需要先转化为 $x_i-x_j\le k-1$ 的形式连边。反之亦然。
• 只有等号的情况：建双向边即可。即转化为 $x_i-x_j\le k$ 和 $x_i-x_j\ge k$ 的形式。

例题 1

[SCOI2011]糖果
传送门

思路

可以很轻易地根据差分约束系统建模。

这道题并不是求特定两个数之间的最小值，求得是最小值的总和，只需要把 dis 数组中的值加起来即为答案。

注意要开 long long，否则会 WA 一个点。

完整代码

#include <bits/stdc++.h>

using namespace std;

const int maxN = 1e5 + 5;

struct Edge {
    int next, to, val;
} edge[maxN << 1];

int head[maxN], neg[maxN];
int cnt, n, k;
bool used[maxN];
long long ans, dis[maxN];
queue<int> que;

void add(int from, int to, int val) {
    edge[++cnt] = (Edge) {head[from], to, val};
    head[from] = cnt;
}

bool lpfa() {
    while (!que.empty()) {
        int u = que.front();
        que.pop(); used[u] = false;
        for (int i = head[u]; ~i; i = edge[i].next) {
            int v = edge[i].to;
            if (dis[v] < dis[u] + edge[i].val) {
                dis[v] = dis[u] + edge[i].val;
                neg[v]++;
                if (neg[v] >= n) return false;
                if (!used[v]) {
                    used[v] = true;
                    que.push(v);
                }
            }
        }
    }
    return true;
}

int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++) {
        int opt, a, b;
        scanf("%d%d%d", &opt, &a, &b);
        if (opt == 1) {add(a, b, 0); add(b, a, 0);}
        else if (opt == 2) add(a, b, 1);
        else if (opt == 3) add(b, a, 0);
        else if (opt == 4) add(b, a, 1);
        else if (opt == 5) add(a, b, 0);
        if ((opt == 2 || opt == 4) && a == b) {
            printf("-1\n");
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        neg[i]++, dis[i] = 1;
        used[i] = true;
        que.push(i);
    }
    if (!lpfa()) {
        printf("-1\n");
    } else {
        for (int i = 1; i <= n; i++)
            ans += dis[i];
        printf("%lld\n", ans);
    }
    return 0;
}

例题 2

种树
传送门

思路

如何建模？我们可以利用前缀和，建立 sum[b] 与 sum[e] 的关系。根据读入描述可建立模型 $s_e-s_{b-1}\ge t$ （为什么要减去 1？因为是闭区间 QwQ）。

其中还有一个隐含条件，就是每座房子前最多种一棵树，所以有了这样的不等式 $0\le s_i-s_{i-1} \le 1$，稍微转化一下就是两个不等式 $s_i-s_{i-1}\ge 0$ 和 $s_{i-1}-s_i\ge -1$。

需要建立一个超级源点向所有点连权值为 0 的边，这样从超级源点跑一遍最长路，最后 dis[n] 即为解。

完整代码

#include <bits/stdc++.h>

using namespace std;

const int maxN = 3e4 + 5;
const int INF = 0x3f3f3f3f;

struct Edge {
    int next, to, val;
} edge[maxN];

int head[maxN], dis[maxN];
int cnt, n, h;
bool used[maxN];
queue<int> que;

void add(int from, int to, int val) {
    edge[++cnt] = (Edge) {head[from], to, val};
    head[from] = cnt;
}

void lpfa(int s) {
    fill(dis, dis + n + 2, -INF);
    que.push(s);
    dis[s] = 0, used[s] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop(); used[u] = false;
        for (int i = head[u]; ~i; i = edge[i].next) {
            int v = edge[i].to;
            if (dis[v] < dis[u] + edge[i].val) {
                dis[v] = dis[u] + edge[i].val;
                if (!used[v]) {
                    que.push(v);
                    used[v] = true;
                }
            }
        }
    }
}

int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &h);
    int s = n + 1;
    for (int i = 1; i <= h; i++) {
        int a, b, t;
        scanf("%d%d%d", &a, &b, &t);
        add(a - 1, b, t);
    }
    for (int i = 1; i <= n; i++) {
        add(i - 1, i, 0);
        add(i, i - 1, -1);
    }
    for (int i = 0; i <= n; i++)
        add(s, i, 0);
    lpfa(s);
    printf("%d\n", dis[n]);
    return 0;
}