计蒜客-闯关游戏

2019-08-05

算法

单源最长路径 , 图 , spfa , spfa判环

蒜头君在玩一个很好玩的游戏，这个游戏一共有至多 100 个地图，其中地图 1 是起点，房间 n 是终点。有的地图是补给站，可以加 k_i 点体力，而有的地图里存在怪物，需要消耗 k_i 点体力，地图与地图之间存在一些单向通道连接。

蒜头君从 1 号地图出发，有 100 点初始体力。每进入一个地图的时候，需要扣除或者增加相应的体力值。这个过程持续到走到终点，或者体力值归零就会 Game Over。不过，他可以经过同个地图任意次，且每次都需要接受该地图的体力值。

输入格式

第 1 行一个整数 n (n ≤100)。

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

输出格式

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

样例输入

样例输出

No

并不是只要有正环就能确保一定能到达终点, 有如下2中情况:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

//----------------------------------
// 点权图
// 价值最大路径

const int INF = 0x3f3f3f3f;
const int N = 101;

struct edge {
    int v, next;
    edge() {}
    edge(int _v, int _next) : v(_v), next(_next) {}
} E[N * N];

int p[N];
int eid;

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

void insert(int u, int v) {
    E[eid] = edge(v, p[u]);
    p[u] = eid++;
}

int value[N];
int w[N];
int cnt[N];
bool vis[N];
queue<int> q;


bool spfa(int s, int n) {
    memset(value, 0, sizeof value);
    memset(vis, false, sizeof vis);
    memset(cnt, 0, sizeof cnt);
    value[s] = 100 + w[s];
    vis[s] = true;
    cnt[s]++;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        if (cnt[u] == n) { //第一次发现点在正环上, 将value[u] 置为 INF
            value[u] = INF;
        } else if (cnt[u] == n + 1) { //第二次发现点在正环上, 直接跳过该点
            continue;
        }

        if (u == n) {
            return true;
        }

        for (int e = p[u]; e != -1; e = E[e].next) {
            int v = E[e].v;
            if (value[v] < value[u] + w[v]) {
                value[v] = value[u] + w[v];
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                    cnt[v]++;
                }
            }
        }
    }

    return false;
}


int main() {
    int n, k, v;
    init();
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> k;
        while (k--) {
            cin >> v;
            insert(i, v);
        }
    }

    cout << (spfa(1, n) ? "Yes" : "No") << endl;
    return 0;
}