摘要
Title: 852. spfa判断负环
Tag: 负环、spfa
Memory Limit: 64 MB
Time Limit: 1000 ms

852. spfa判断负环

题意

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
请你判断图中是否存在负权回路。
思路

求负环的常用方法，基于SPFA，一般都用方法 2（该题也是用方法 2）：
- 方法 1：统计每个点入队的次数，如果某个点入队n次，则说明存在负环
- 方法 2：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则也说明存在环
  在更新dist最短路时，更新cnt数组——代表此最短路经历了多少边，当 $cnt[i] >= n$ 时，说明有负环出现，因为说明经历了n条边，n+1个点，而一共n个点，所以一定会有两个点重复，所以一定会有负环
注意：
- 为什么一开始要将所有点入队？
  - 因为不知道起点是哪里，可能从任一点开始遍历不到负环，所以要一开始把所有点都入队
  - 其实也就相当于在原图的基础上新建一个虚拟源点，从该点向其他所有点连一条权值为0的有向边。那么原图有负环等价于新图有负环。此时在新图上做spfa，将虚拟源点加入队列中。然后进行spfa的第一次迭代，这时会将所有点的距离更新并将所有点插入队列中。执行到这一步，就等价于视频中的做法了。那么视频中的做法可以找到负环，等价于这次spfa可以找到负环，等价于新图有负环，等价于原图有负环。得证。

代码

'''
Author: NEFU AB-IN
Date: 2022-03-03 12:41:05
FilePath: \ACM\Acwing\852.py
LastEditTime: 2022-03-03 13:06:28
'''

from collections import deque

N = int(1e5 + 10)
INF = int(2e9)
st, dist, cnt = [0] * N, [INF] * N, [0] * N
g = [[] for _ in range(N)]
q = deque()


def spfa():
    for i in range(1, n + 1):
        q.appendleft(i)
        st[i] = 1
    while q:
        u = q.pop()
        st[u] = 0
        for v, w in g[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                cnt[v] = cnt[u] + 1
                if cnt[v] >= n:
                    return True
                if st[v] == 0:
                    q.appendleft(v)
                    st[v] = 1
    return False


n, m = map(int, input().split())
for i in range(m):
    x, y, z = map(int, input().split())
    g[x].append([y, z])
if spfa():
    print("Yes")
else:
    print("No")

852. spfa判断负环

题意

思路

代码