题解 P3385 【【模板】负环】
Suuon_Kanderu
2020-08-23 15:20:52
模板题为啥没人来发题解啊……
反正 SPFA 也已经是 $O(VE)$ 了，所以我们直接写 BellmanFord 也只是差个常数而已。
BellmanFord 的算法流程是这样的：
1. 初始化，设 $d_i$ 为 1 到 n 的最短路距离，肯定是 $d_1 = 0, d_{2 \cdots n} = \operatorname{inf}$。
2. 进行 $n-1$ 次松弛操作。我们每次就更新一层数的最短路。什么意思呢？
比如这个垃圾图，第一次，我们就会把 $d_B$ 更新为 $f$ ，第二次操作时就会把 $d_C$ 更新为 $f+g$。
具体实现就可以用 for 循环扫一遍所有的边。当然你用什么 SPFA 的就是用队首更新点。
3. 到了我们判断负环的时间了。
我们把所有边扫一遍，由于题目说 **从顶点 1 出发能到达的负环**，所以我们直接掠过顶点 1 无法到达的点，（$d_i = \operatorname{inf}$）。按理说，$n-1$ 次松弛之后我们一定无法获得更短的路了(都被松弛过了)。然而，如果存在负环，就没有最短路了，因为在负环上能够越走越短，**所以此时如果能够松弛，一定存在负环**
代码：
```
#include <cstdio>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 1000;
int cnt = 0;
struct node{
int x , y , v;
}e[N];
void add(int x ,int y , int v) {e[++cnt] = {x , y , v};}
void addd(int x, int y , int v) {
if(v < 0)add(x , y , v);
if(v >= 0) add(x , y , v) , add(y , x , v);
}
int n;
bool bellman() {
static int d[N];
d[1] = 0;
for(int i = 2; i <= n; i++)
d[i] = 0x7fffffff;
for(int i = 1 ; i <= n - 1; i++)
for(int j = 1; j <= cnt; j++) {
if(d[e[j].x] != 0x7fffffff &&
d[e[j].x] + e[j].v < d[e[j].y])
d[e[j].y] = d[e[j].x] + e[j].v;
}
for(int i = 1; i <= cnt; i++) {
if(d[e[i].x] == 0x7fffffff || d[e[i].y] == 0x7fffffff)continue;
if(d[e[i].x] + e[i].v < d[e[i].y])return true;// 负权回路
}
return false;
}
signed main() {
int t;scanf("%d" , &t);
while(t--) {
memset(e , 0 , sizeof(e));
cnt = 0;
int m;scanf("%d%d" , &n, &m);
for(int i = 1; i <= m; i++) {
int x , y , v;scanf("%d%d%d" , &x , &y , &v);
addd(x , y , v);
}
if(bellman())printf("YES\n");
else printf("NO\n");
}
return 0;
}
```