本文写于 2020年04月08日,距今已超过 1 年,距 2020年04月08日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

计蒜客 – 蒜头君的银行卡 | 算尽天下系列第 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;
}
0 0 投票数
评分
2条留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
2 评论
内联反馈
查看所有评论
Xiejiadong
Xiejiadong (@guest_2145) Chrome 80.0.3987.163 Mac OS X 10_14_2
游客
2020年4月8日 15:12

长老怎么不写一些 留学申请的经验