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

预计阅读时间: 5 分钟 644 次阅读 1075 字 最后更新于 2023-02-22 算法与数据结构


[USACO06DEC]Wormholes G

题目背景

英文题面见此链接

题目描述

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

John 的每个农场有 m 条小路(无向边)连接着 n 块地(从 1n 标号),并有 w 个虫洞。

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

输入格式

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

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

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

每组数据的第 2 到第 (m+1) 行,每行有三个用空格隔开的整数 u,v,p,代表有一条连接 uv 的小路,经过这条路需要花费 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 只需要沿着 1231 的路径一直转圈即可,每转完一圈,时间就会减少一秒。

数据范围与约定

对于 100% 的数据,1T51n5001m25001w2001p104

分析

这道题目存在着两种道路,一种是连接双向边的花费为正的道路,另一种是连接单向边花费为负的虫洞,题目要求我们找到一个花费为负的道路。其实就是一个裸的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