计蒜客 – 蒜头君的银行卡 | 算尽天下系列第 10 期 | SPFA – 差分约束系统

上一期，长老向大家分享了一个跟 BFS 很像的、可以求解负环的单源最短路算法 SPFA，今天，让我们来看一下 SPFA 在求解差分约束系统时的力量吧。

如果一个不等式组由 $n$ 个变量和 $m$ 个约束条件组成，且每个约束条件都是形如 $x_i-x_j\leq k,1\leq i,j\leq n$ 的不等式，则称其为差分约束系统 (system of difference constraints)。

差分约束系统是求解一组变量的不等式组的算法，是最短路的一类经典应用。

为什么说它是最短路的一类经典应用呢？第一眼看过去难道不是一个数学问题吗？实际上，我们在求解差分约束系统时，可以将其转化为图论中单源最短路（或最长路）问题。

在求解最短路问题时，我们经常写的一个不等式是 $d_u+w_{u,v} \geq d_v$，移项可得 $d_v-d_u\leq w_{u,v}$，这类似于不等式组中的 $x_j-x_i\leq k$。所以我们可以理解成从顶点 $u$ 到顶点 $v$ 连一条权值为 $w_{u,v}$ 的边，用最短路算法得到最短路的答案 $d_i$，也就求出了原不等式组的一个解。

因此我们可以将每个变量 $x_i$ 作为一个顶点，对于约束条件 $x_j-x_i\leq k$，连接一条边权为 $k$ 的有向边 <i, j> 。

连边有两种方式，第一种是连边后求最长路，第二种是连边后求最短路。

对于 $x_j – x_i \leq k$，若求最长路，则变形为 $x_j -k\leq x_i$，从 $j$ 到 $i$ 连一条权值为 $k$ 的边；若求最短路，则变形为 $x_i+k\geq x_j$，从 $i$ 到 $j$ 连一条权值为 $k$ 的边。

我们再增加一个超级源 $s$，$s$ 连向其余每个顶点，边权均为 $0$。

对这个图执行单源最短路算法，如果程序正常结束，那么得到的最短路答案数组 d[i] 就是满足条件的一组解；若图中存在负环，则该不等式组无解。

考虑到差分约束系统的边权可能为负，我们套用前面介绍的 SPFA 算法可解决这个问题。

在学习了使用 SPFA 求解差分约束系统之后，让我们来看一道例题，“计蒜客”的“蒜头君的银行卡”。

虽然蒜头君并没有多少钱，但是蒜头君办了很多张银行卡，共有 $n$ 张，以至于他自己都忘记了每张银行卡里有多少钱了。

他只记得一些含糊的信息，这些信息主要以下列三种形式描述：

1. 银行卡 $a$ 比银行卡 $b$ 至少多 $c$ 元。
2. 银行卡 $a$ 比银行卡 $b$ 至多多 $c$ 元。
3. 银行卡 $a$ 和银行卡 $b$ 里的存款一样多。

但是由于蒜头君的记忆有些差，他想知道是否存在一种情况，使得银行卡的存款情况和他记忆中的所有信息吻合。

输入格式

第一行输入两个整数 $n$ 和 $m$，分别表示银行卡数目和蒜头君记忆中的信息的数目。$(1\leq n,m\leq 10000)$

接下来 $m$ 行：

• 如果每行第一个数是 $1$，接下来有三个整数 $a, b, c$，表示银行卡 $a$ 比银行卡 $b$ 至少多 $c$ 元。
• 如果每行第一个数是 $2$，接下来有三个整数 $a, b, c$，表示银行卡 $a$ 比银行卡 $b$ 至多多 $c$ 元。
• 如果每行第一个数是 $3$，接下来有两个整数 $a, b$，表示银行卡 $a$ 和 $b$ 里的存款一样多。$(1\leq n,m,a,b,c\leq 10000)$

3 3
3 1 2
1 1 3 1
2 2 3 2

输出格式

如果存在某种情况与蒜头君的记忆吻合，输出 Yes，否则输出 No。

Yes

这道题唯一的难点在于将不等式的表达形式转换成图中的边，一旦正确地插入了边，那么直接套用 SPFA 的模板就可以了，不需要做任何其他的修改。

我们先来分析一下 $a$ 和 $b$ 中钱一样多的情况。若 $a = b$，则等价于 $a \leqslant b $ 且 $ b \leqslant a$，那么我们可以往图中插入一条从 $a$ 到 $b$ 的权重为 $0$ 的边，以及一条从 $b$ 到 $a$ 的权重为 $0$ 的边。

if (type == 3) {
    // (a == b) 等价于 (a <= b && b <= a)
    insert(a, b, 0);
    insert(b, a, 0);
}

若 $a$ 比 $b$ 至少多 $c$ 元，那么有 $a – b \geqslant c$，移项得到 $b – a \leqslant -c$，即 $a + (-c) \geqslant b$，对照上面的公式可以发现，应该从 $a$ 到 $b$ 连一条权值为 $-c$ 的边，求最短路；类似地，若 $a$ 比 $b$ 至多多 $c$ 元，那么 $a – b \leqslant c$ 可得 $b + c >= a$，从 $b$ 到 $a$ 连一条权值为 $c$ 的边，求最短路。

if (type == 1) {
    // a 比 b 至少多 c 元：(a - b >= c) => (b - a <= -c) => (a + (-c) >= b)，从 a 到 b 连一条权值为 -c 的边，求最短路
    insert(a, b, -c);
} else {
    // a 比 b 至多多 c 元：(a - b <= c) => (a - c <= b) => (b + c >= a)，从 b 到 a 连一条权值为 c 的边，求最短路
    insert(b, a, c);
}

在正确插入所有的边以后，加上一个超级源：

for (int i = 1; i <= n; i++) {
    insert(0, i, 0); // 插入超级源，连向每一个点，权重为 0
}

并且在 SPFA 的模板中修改 cnt[v] == n 时的情况：

if (cnt[v] == n + 1) {
    // 因为加入了超级源点，所以一共是 n + 1 个点
    // 出现负环，不等式组无解
    printf("No");
    exit(0);
}

其余的部分均直接套用 SPFA 模板，模板代码可参见前一篇文章。

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3F3F3F3F;

const int MAX_N = 10007;
const int MAX_M = 10007;
bool inq[MAX_N];
int d[MAX_N];  // 如果到顶点 i 的距离是 0x3F3F3F3F，则说明不存在源点到 i 的最短路
int cnt[MAX_N];
int n;

struct edge {
    int v, next, w;
} e[MAX_M];
int p[MAX_N], eid;

void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}

void insert(int u, int v, int w) {
    e[eid].v = v;
    e[eid].next = p[u];
    e[eid].w = w;
    p[u] = eid++;
}

// SPFA 算法
void spfa(int s) {
    memset(inq, 0, sizeof(inq));
    memset(d, 0x3F, sizeof(d));
    memset(cnt, 0, sizeof(cnt));
    d[s] = 0;
    inq[s] = true;
    queue<int> q;
    q.push(s);
    cnt[s]++;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (int i = p[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (d[u] + e[i].w < d[v]) {
                d[v] = d[u] + e[i].w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                    cnt[v]++;
                    if (cnt[v] == n + 1) {
                        // 因为加入了超级源点，所以一共是 n + 1 个点
                        // 出现负环，不等式组无解
                        printf("No");
                        exit(0);
                    }
                }
            }
        }
    }
}

int main() {
    int m;
    scanf("%d%d", &n, &m);
    init();
    for (int i = 0; i < m; i++) {
        int type;
        int a, b;
        scanf("%d%d%d", &type, &a, &b);
        if (type == 3) {
            // (a == b) 等价于 (a <= b && b <= a)
            insert(a, b, 0);
            insert(b, a, 0);
        } else {
            int c;
            scanf("%d", &c);
            if (type == 1) {
                // a 比 b 至少多 c 元：(a - b >= c) => (b - a <= -c) => (a + (-c) >= b)，从 a 到 b 连一条权值为 -c 的边，求最短路
                insert(a, b, -c);
            } else {
                // a 比 b 至多多 c 元：(a - b <= c) => (a - c <= b) => (b + c >= a)，从 b 到 a 连一条权值为 c 的边，求最短路
                insert(b, a, c);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        insert(0, i, 0); // 插入超级源，连向每一个点，权重为 0
    }

    // 从起点开始做单源最短路
    spfa(1);

    // 如果程序正常结束，那么得到的最短路答案数组就是满足条件的一组解
    printf("Yes");
    return 0;
}