python/TangDou/AcWing/ShortestPath/852.md

##[$AcWing$ $852$. $spfa$判断负环](https://www.acwing.com/problem/content/854/)

### 一、题目描述
给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

**输入格式**
第一行包含整数 $n$ 和 $m$。

接下来 $m$ 行每行包含三个整数 $x,y,z$，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$。

**输出格式**
如果图中存在负权回路，则输出 `Yes`，否则输出 `No`。

**数据范围**
$1≤n≤2000,1≤m≤10000$,
图中涉及边长绝对值均不超过 $10000$。

**输入样例：**
```cpp {.line-numbers}
3 3
1 2 -1
2 3 4
3 1 -4
```

**输出样例：**
```cpp {.line-numbers}
Yes
```

### 二、解题思路
1. $spfa$可以用来**判断是不是有向图中存在负环**。

2. 基本原理：利用 **抽屉原理**

    $dist[x]$的概念是指当前从虚拟源点到$x$号点的最短路径的长度。$dist[x]=dist[t]+w[i]$

    $cnt[x]$的概念是指当前从虚拟源点到$x$号点的最短路径的边数量。$cnt[x]=cnt[t]+1$
   
    如果发现$cnt[x]>=n$,就意味着从虚拟源点$\sim x$经历了$n$条边，那么必须经过了$n+1$个点，但问题是点一共只有$n$个，所以必然有两个点是相同的，就是有一个环。
    因为是在不断求最短路径的过程中发现了环，路径长度在不断变小的情况下发现了环，那么，只能是负环。

3. 为什么初始化时初始值为$0$,而且把所有结点都加入队列？
    在原图的基础上新建一个**虚拟源点**，从该点向其他所有点连一条权值为$0$的有向边。那么原图有负环等价于新图有负环。此时在新图上做$spfa$，将虚拟源点加入队列中。然后进行$spfa$的第一次迭代，这时会将所有点的距离更新并将所有点插入队列中。执行到这一步，就等价于下面代码中的做法了。如果新图有负环，等价于原图有负环。

### 三、实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 10010;
int n, m;   // 点数、边数
int d[N];   // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
int cnt[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++;
}

int spfa() {
    queue<int> q;
    // 构建超级源点，防止负环与出发点不连通
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
    }
    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 (d[v] > d[u] + w[i]) {
                d[v] = d[u] + w[i];

                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return 1;
                if (!st[v]) {
                    q.push(v);
                    st[v] = 1;
                }
            }
        }
    }
    return 0;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    // 调用spfa判断是否有负环
    if (spfa())
        puts("Yes");
    else
        puts("No");

    return 0;
}
```