SPFA判断负环 [USACO06DEC]Wormholes G题解

发布于 2023-02-22  430 次阅读

[USACO06DEC]Wormholes G

题目背景

英文题面见此链接

题目描述

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。

John 的每个农场有 $m$ 条小路（无向边）连接着 $n$ 块地（从 $1 \sim n$ 标号），并有 $w$ 个虫洞。

现在 John 希望能够从某块地出发，走过一条路径回到出发点，且同时也回到了出发时刻以前的某一时刻。请你告诉他能否做到。

输入格式

输入的第一行是一个整数 $T$，代表测试数据的组数。

每组测试数据的格式如下：

每组数据的第一行是三个用空格隔开的整数，分别代表农田的个数 $n$，小路的条数 $m$，以及虫洞的个数 $w$。

每组数据的第 $2$ 到第 $(m + 1)$ 行，每行有三个用空格隔开的整数 $u, v, p$，代表有一条连接 $u$ 与 $v$ 的小路，经过这条路需要花费 $p$ 的时间。

每组数据的第 $(m + 2)$ 到第 $(m + w + 1)$ 行，每行三个用空格隔开的整数 $u, v, p$，代表点 $u$ 存在一个虫洞，经过这个虫洞会到达点 $v$，并回到 $p$ 秒之前。

输出格式

对于每组测试数据，输出一行一个字符串，如果能回到出发时刻之前，则输出 YES，否则输出 NO。

样例 #1

样例输入 #1

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

样例输出 #1

NO
YES

提示

样例 2 解释

John 只需要沿着 $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ 的路径一直转圈即可，每转完一圈，时间就会减少一秒。

数据范围与约定

对于 $100\%$ 的数据，$1 \le T \le 5$，$1 \le n \le 500$，$1 \le m \le 2500$，$1 \le w \le 200$，$1 \le p \le 10^4$

分析

这道题目存在着两种道路，一种是连接双向边的花费为正的道路，另一种是连接单向边花费为负的虫洞，题目要求我们找到一个花费为负的道路。其实就是一个裸的SPFA判断负环的题。这里介绍一下DFS版本SPFA判断负环。

DFS版的SPFA应用可能就只有判负环了，它判断负环的时间复杂度为$O(m)$，正常的SPFA开一个数组要记录每个节点被进队的次数，如果某个节点被的次数大于n，则一定存在负环。因为一个节点最多与n-1个节点连边，不存在负权边，最多被松弛n-1次，加上刚开始进队一次，如果超过了n次，则一定存在负环，使得SPFA每走一次都能得到更小的结果。

而DFS版本的SFPA更加简单，它只需要看现在更新答案的节点之前有没有访问过，如果已经访问过，那么一定存在负环。

CODE

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 8000;

struct node
{
    int next, to, data;
} edge[maxn];
int head[maxn], n, m, w, cnt = 0;

inline void add_edge(int from, int to, int data)
{
    edge[++cnt] = (node){head[from], to, data};
    head[from] = cnt;
}

int vis[maxn] = {}, dis[maxn];

bool dfs(int x)  // SPFA
{
    if (vis[x])
        return true;
    vis[x] = true;
    for (register int i = head[x]; i; i = edge[i].next)
    {
        if (dis[edge[i].to] > dis[x] + edge[i].data)
        {
            dis[edge[i].to] = dis[x] + edge[i].data;
            if (dfs(edge[i].to))
                return true;
        }
    }
    vis[x] = false;
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t --> 0)
    {
        cnt = 0;
        cin >> n >> m >> w;
        for (register int i = 0; i < maxn; i++) // 多测清空
        {
            head[i] = 0;
            edge[i] = (node){0, 0, 0};
            vis[i] = 0;
            dis[i] = 2147483647;
        }
        for (register int i = 1, u, v, p; i <= m; i++)
        {
            cin >> u >> v >> p;
            add_edge(u, v, p);
            add_edge(v, u, p);
        }
        for (register int i = 1, u, v, p; i <= w; i++)
        {
            cin >> u >> v >> p;
            add_edge(u, v, -p);
        }
        for (register int i = 1; i <= n; i++) // 设立超级原点
            add_edge(n + 1, i, 0);
        dis[n + 1] = 0;
        if (dfs(n + 1))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

$end$