算法|题解

计蒜客 – 闯关游戏

凝神长老 · 4月7日 · 2020年 · · · · · · · · 604次已读

今天分享一道有关 SPFA 单源最短路的算法题。

蒜头君在玩一个很好玩的游戏,这个游戏一共有至多 $100$ 个地图,其中地图 $1$ 是起点,房间 $n$ 是终点。有的地图是补给站,可以加 $k_i$ 点体力,而有的地图里存在怪物,需要消耗 $k_i$ 点体力,地图与地图之间存在一些单向通道链接。 蒜头君从 $1$ 号地图出发,有 $100$ 点初始体力。每进入一个地图的时候,需要扣除或者增加相应的体力值。这个过程持续到走到终点,或者体力值归零就会 Game Over。不过,他可以经过同个地图任意次,且每次都需要接受该地图的体力值。

输入格式

第 $1$ 行一个整数 $n$ ($n\leq 100$)。

第 $2$ ~ $n+1$ 行,每行第一个整数表示该地图体力值变化。接下来是从该房间能到达的房间名单,第一个整数表示房间数,后面是能到达的房间编号。

5
0 1 2
-60 1 3
-60 1 4
20 1 5
0 0

输出格式

若玩家能到达终点,输出 Yes,否则输出 No

No

首先我们来看一下什么是 SPFA。

众所周知,Dijkstra 算法不能处理有负权的图,而 Bellman-ford 算法通过对图进行 $|V| – 1$ 次松弛操作,得到所有可能的最短路径,而 SPFA(Shortest Path Faster Algorithm)通常被认为是 Bellman-ford 算法的队列优化,在代码形式上接近于宽度优先搜索 BFS,是一个在实践中非常高效的单源最短路算法。

需要指出的是,SPFA 的本质是 Bellman-ford 算法的队列优化,由于 SPFA 没有改变 Bellaman-ford 的时间复杂度,国外一般来说不认为 SPFA 是一个新的算法,而仅仅是 Bellman-ford 的队列优化。

在一定程度上,可以认为 SPFA 是由 BFS 的思想转化而来:从不含边权或者说边权为 1 个单位长度的图上的 BFS,推广到带权图上,就得到了 SPFA。SPFA 与 BFS 的不同在于,BFS 中一个点出了队列就不可能重新进入队列,但是 SPFA 中一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本身被改进,于是再次用来改进其它的点,这样反复迭代下去。

SPFA 可以处理任意不含负环(负环是指总边权和为负数的环)的图的最短路,并能判断图中是否存在负环。

有了 BFS 的基础,我们很容易得到 SPFA 的算法描述:

  1. d[i] 表示从源点 $s$ 到顶点 $i$ 的最短路,队列 q 保存即将进行拓展的顶点列表,inq[i] 标识顶点 $i$ 是不是在队列中;
  2. 初始队列中仅包含源点 $s$,且源点 $s$ 的 d[s] = 0
  3. 取出队列头顶点 $u$,扫描从顶点 $u$ 出发的每条边,设每条边的另一端为 $v$,边 <u,v> 权值为 $w$,若 d[u] + w < d[v],则 将 d[v] 修改为 d[u] + w,若 $v$ 不在队列中,则将 $v$ 入队。重复步骤直到队列为空。
  4. 最终 d[] 数组就是从源点出发到每个顶点的最短路距离。如果一个顶点从没有入队,则说明没有从源点到该顶点的路径。
void spfa(int s) {
    memset(inq, 0, sizeof(inq));
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    inq[s] = true;
    queue<int> q;
    q.push(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;
                }
            }
        }
    }
}

在进行 SPFA 时,用一个数组 cnt[i] 来标记每个顶点入队次数。如果一个顶点入队次数 cnt[i] 大于顶点总数 $n$,则表示该图中包含负环。

很显然,SPFA 的空间复杂度为 $\mathcal{O}(V)$。如果顶点的平均入队次数为 $k$,则 SPFA 的时间复杂度为 $\mathcal{O}(kE)$,对于较为随机的稀疏图,根据经验 $k$ 一般不超过 $4$。

对于稀疏图而言,SPFA 相比堆优化的 Dijkstra 有很大的效率提升,但是对于稠密图而言,SPFA 最坏为 $\mathcal{O}(VE)$,远差于堆优化 Dijkstra 的 $\mathcal{O}((V+E)logV)$。

在看完了 SPFA 之后,这道题就比较容易了。

在套用 SPFA 模板的时候,注意要初始化 d[] 数组为负无穷大,并设置起点的体力值为 d[s] = 100

然后在 SPFA 的判断条件中 if (d[u] + e[i].w < d[v]) 改成 if (d[u] + e[i].w > d[v]) 因为我们需要保留体力最大的。

另外在每一个点入队以后,令 cnt[i]++,若等于 $n$,说明有环,那么蒜头君就可以无限制地往这个点走,最终体力为无穷大,再也不需要考虑其他点的体力值了,因此一定可以走到终点。所以直接 return,并直接输出 Yes

最后的输出结果就是 d[n] > 0

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3F3F3F3F;

const int MAX_N = 100;
const int MAX_M = 10000;
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;
    d[s] = 100; // 套用模板,初始体力是 100
    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]) {
            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) {
                        // 如果一个点入队 n 次,说明这个点能无限增加体力
                        // 置终点的剩余体力为无穷大
                        d[n] = INF;
                        return;
                    }
                }
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    init();
    // 本题 id 从 1 开始
    for (int i = 1; i <= n; i++) {
        int hp, rooms, to;
        scanf("%d%d", &hp, &rooms);
        for (int j = 0; j < rooms; j++) {
            scanf("%d", &to);
            insert(i, to, hp);
        }
    }

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

    // 最终输出的结果是:达到终点的时候体力还大于 0 吗
    printf("%s", d[n] > 0 ? "Yes" : "No");
}
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论