|
|
## [$AcWing$ $904$ 虫洞](https://www.acwing.com/problem/content/906/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
农夫约翰在巡视他的众多农场时，发现了很多令人惊叹的虫洞。
|
|
|
|
|
|
虫洞非常奇特，它可以看作是一条 **单向** 路径，通过它可以使你回到过去的某个时刻（相对于你进入虫洞之前）。
|
|
|
|
|
|
农夫约翰的每个农场中包含 $N$ 片田地，$M$ 条路径（**双向**）以及 $W$ 个虫洞。
|
|
|
|
|
|
现在农夫约翰希望能够从农场中的某片田地出发，经过一些路径和虫洞回到过去，并在他的出发时刻之前赶到他的出发地。
|
|
|
|
|
|
他希望能够看到出发之前的自己。
|
|
|
|
|
|
请你 **判断** 一下约翰能否做到这一点。
|
|
|
|
|
|
下面我们将给你提供约翰拥有的农场数量 $F$，以及每个农场的完整信息。
|
|
|
|
|
|
已知走过任何一条路径所花费的时间都不超过 $10000$ 秒，任何虫洞将他带回的时间都不会超过 $10000$ 秒。
|
|
|
|
|
|
**输入格式**
|
|
|
第一行包含整数 $F$，表示约翰共有 $F$ 个农场。
|
|
|
|
|
|
对于每个农场，第一行包含三个整数 $N,M,W$。
|
|
|
|
|
|
接下来 $M$ 行，每行包含三个整数 $S,E,T$，表示田地 $S$ 和 $E$ 之间存在一条路径，经过这条路径所花的时间为 $T$。
|
|
|
|
|
|
再接下来 $W$ 行，每行包含三个整数 $S,E,T$，表示存在一条从田地 $S$ 走到田地 $E$ 的虫洞，走过这条虫洞，可以回到 $T$ 秒之前。
|
|
|
|
|
|
**输出格式**
|
|
|
输出共 $F$ 行，每行输出一个结果。
|
|
|
|
|
|
如果约翰能够在出发时刻之前回到出发地，则输出 `YES`，否则输出 `NO`。
|
|
|
|
|
|
**数据范围**
|
|
|
$1≤F≤5$
|
|
|
|
|
|
$1≤N≤500,1≤M≤2500,1≤W≤200,1≤T≤10000,1≤S,E≤N$
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
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
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
NO
|
|
|
YES
|
|
|
```
|
|
|
|
|
|
### 二、解题思路
|
|
|
|
|
|
使用$spfa$算法解决 **是否存在负环**
|
|
|
|
|
|
基于$SPFA$，一般都用方法 $2$：
|
|
|
|
|
|
* 方法 $1$：统计每个点入队的次数，如果某个点入队$n$次，则说明存在 **负环**
|
|
|
* 方法 $2$：<font color='red' size=4><b>【荐】</b></font>统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于$n$，说明存在 **负环**
|
|
|
|
|
|
|
|
|
#### 通用做法
|
|
|
在原图的基础上新建一个虚拟源点，从该点向其他所有点连一条权值为$0$的有向边。那么原图有负环等价于新图有负环。此时在新图上做$spfa$，将虚拟源点加入队列中。然后进行$spfa$的第一次迭代，这时会将所有点的距离更新并将所有点插入队列中。执行到这一步，就等价于$y$总视频中的做法了。此做法可以找到负环，等价于原图有负环。
|
|
|
|
|
|
|
|
|
#### 算法步骤
|
|
|
* $1、dist[x]$ 记录虚拟源点到$x$的最短距离
|
|
|
|
|
|
* $2、cnt[x]$ 记录当前$x$点到虚拟源点最短路的边数，初始每个点到虚拟源点的距离为$0$，只要他能再走$n$步，即$cnt[x] >= n$，则表示该图中一定存在负环，由于从虚拟源点到$x$至少经过$n$条边时，则说明图中至少有$n + 1$个点，表示一定有点是重复使用
|
|
|
|
|
|
* $3、$若$dist[j] > dist[t] + w[i]$,则表示从$t$点走到$j$点能够让权值变少，因此进行对该点$j$进行更新，并且对应$cnt[j] = cnt[t] + 1$,往前走一步
|
|
|
|
|
|
> **注意**：该题是判断是否存在负环，并非判断是否存在从$1$开始的负环，因此需要将所有的点都加入队列中，更新周围的点,这也是为什么要使用超级源点的原因。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
时间复杂度 一般：$O(m)$ 最坏：$O(nm)$
|
|
|
|
|
|
### $Code$
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 510, M = 5210 * 2;
|
|
|
int n, m1, m2;
|
|
|
int dist[N]; // dist[x]记录源点到x的最短距离
|
|
|
int cnt[N]; // cnt[x]记录源点到x在产生最短距离时的边数
|
|
|
bool st[N];
|
|
|
// 邻接表
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
bool spfa() {
|
|
|
// 初始化距离INF
|
|
|
memset(dist, 0x3f, sizeof dist);
|
|
|
// 是不是已经加入到集合中
|
|
|
memset(st, 0, sizeof st);
|
|
|
// 初始化从源点到x的最短距离时，边数都是0
|
|
|
memset(cnt, 0, sizeof cnt);
|
|
|
|
|
|
queue<int> q;
|
|
|
|
|
|
// 底层相当于有一个虚拟源点0
|
|
|
// 0到 [1,n]的所有点，边权为0，不影响现在的图
|
|
|
// 从虚拟节点0出发，到达所有的1~n，就成为了单源最短路径问题
|
|
|
for (int i = 1; i <= n; i++) q.push(i), st[i] = true;
|
|
|
|
|
|
// spfa
|
|
|
while (q.size()) {
|
|
|
int u = q.front();
|
|
|
q.pop();
|
|
|
st[u] = 0;
|
|
|
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (dist[v] > dist[u] + w[i]) {
|
|
|
dist[v] = dist[u] + w[i];
|
|
|
/*
|
|
|
dist[j]表示j点距离源点的距离，cnt[j]表示从源点到j点经过的边数
|
|
|
cnt[j] = cnt[u] + 1 的意思是 如果距离更新了，那么从源点到j的边数就等于源点到u的边数 + 1
|
|
|
所以通过这个我们可以判断是否存在负环，如果在j，u之间存在负环，那么cnt[j] 会不断加1
|
|
|
|
|
|
我们通过判断cnt[j] >= n 确定是否存在负环
|
|
|
|
|
|
为什么是cnt[j] >= n ？ 因为cnt数组表示的是边数，如果从某点到j点的边数大于等于n，那么在源点和j点之间肯定存在n+1个点，
|
|
|
但是最多只有n个点，根据抽屉原理，所以必然有点重复出现，存在负环 ！
|
|
|
*/
|
|
|
cnt[v] = cnt[u] + 1;
|
|
|
if (cnt[v] > n) return 1;
|
|
|
|
|
|
if (!st[v]) {
|
|
|
q.push(v);
|
|
|
st[v] = 1;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int T;
|
|
|
scanf("%d", &T);
|
|
|
while (T--) {
|
|
|
scanf("%d %d %d", &n, &m1, &m2);
|
|
|
// 初始化邻接表
|
|
|
memset(h, -1, sizeof h);
|
|
|
idx = 0;
|
|
|
|
|
|
int a, b, c;
|
|
|
// 田地 双向边
|
|
|
while (m1--) {
|
|
|
scanf("%d %d %d", &a, &b, &c);
|
|
|
add(a, b, c), add(b, a, c);
|
|
|
}
|
|
|
|
|
|
// 虫洞 回到t秒前 单向负边
|
|
|
while (m2--) {
|
|
|
scanf("%d %d %d", &a, &b, &c);
|
|
|
add(a, b, -c);
|
|
|
}
|
|
|
|
|
|
// 用spfa判断是不是有负环
|
|
|
spfa() ? puts("YES") : puts("NO");
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
