SPFA求负环

SPFA求负环有两种方法:

1. 统计每个点的入队次数，如果 $\geq n$ 说明存在负环
2. 统计最短路包含的边数，如果 \gen n 说明存在负环

一般使用第 2 种方法，为什么呢? 看这张图

假设每一条边的权重都是 -1 那么这显然是一个负环，而我们用第一种方法要转 n - 1 圈， 第二种只需要转 1 圈
当然这不是绝对的

如果题目给的数据范围很大，有可能会超时怎么办呢？
根据经验，如果所有点的入队次数总和很多，那么很有可能就是有负环。
一般取 N * 2 (小trick)