判断负环详解

什么时候会出现负环：在求从1到x的最短路中，最多有n - 1条边（也就是历经n个点）如果中间出现>=n条边的话
就会出现负环（根据抽屉原理）

抽屉原理（如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。）

维护cnt数组的做用

记录每个点到起点的边数，当cnt[i] >= n 表示出现了边数>=结点数，必然有环，而且一定是负环！

如何判断负环

如果一个点在被入队次数大于 n 次，那么说明存在负环。原理是虽然一个点在状态数组会被多次更新，但是它的更新次数不会大于n-1次，因为从一个点到另一个点最多经过 n-1 条边！如果存在负环则会造成无限入队的情况，spfa算法陷入死循环，这时候就可直接退出了。
个人理解:如果摸一个点的cnt >= n的话说明这个点还没到最后一个点的时候就已经有了n条边了，早就已经符合出现负环的情况了

为什么dist数组不用初始化呢

这里引用y总的原话

有负环的话相当于某些点到起点的距离为负无穷，然后SPFA算法是正确的，且初始时这些点的距离为0,0大于负无穷，所以一定会把这些距离为负无穷的点不断更新。

这里解释一下y总的具体意思，因为有负环的存在所以最终某些点的dist是数组的状态肯定是无穷小的，
而无论dist的初始值为多少肯定都会往无穷小的方向区无限次的更新

负权环

顾名思义，就是一个所有边的边权和为负数的环
当图中有负权环时，队列就不会有空的情况了，因为由于负权环的存在，负权环上的点就可以一直被松弛，一直能被松弛就代表着队列会不断反复让负权环上的点入队出队，程序就会死循环。
而负权环为什么会一直松弛呢
如下图，把2每次经历过的这个负权图的总权值当成2的一个自环的边权，所以2在负权图上转一圈dist减少一点，转无数圈之后，就为无穷小了，所以说如果存在负权图的话，走最短路更新时肯定会绕着负权图转无数次

然而有这样一种情况：由于dis+v<dis才能更新的限制，可能点X更新到Y就卡住，然后放弃更新了。那么这种情况是否会错呢？

答案是否，因为Y这个点肯定已经找过环了，原因如下。

引用一篇博客 https://www.cnblogs.com/hanruyun/p/11361632.html

在测试中笔者还注意到Dfs不管是否存在正环，效果都很好，这可能会让有些读者感到纳闷，按照他们的理解，没有找出正环意味着SPFA算法结束，也就是已经求出最短(长)路，但为什么上文使用Dfs求最短路的效率并没有如此高呢？
这是因为查找正环和求最短路是有区别的。找环时初值应全部赋为0，这将会减少大量无用的计算，效率自然高了不少。有些读者便会怀疑赋初值为0的正确性，会不会由于初值相同而找不到正环，其实这是可以证明的。
首先假设初始时存在一个点s，从该点出发我们能找到正环。下面证明对环上某个点x的重赋值不会对正环的查找产生影响。
假设x在环上的前驱为y。本来在寻找正环时dis[y]+w(y,x)>dis[x]，然后继续从x开始迭代。而如果dis[x]被重赋值了dis[x]’>=dis[y]+w(y,x)，看似迭代到x时就停止了，但其实当x之前被赋为dis[x]’时，就已经可以从x开始继续在环上迭代了，也不需要再从y过渡到x。两者并无区别。依次类推，必然可以找到一个导致正环的起点。
而开始的假设则显然成立，否则我们可以把该正环分成若干段，每段的边权和<=0，与正环的前提矛盾，由此命题得证。

通俗的来讲就是说在走最短路往后更新的过程中可能会有没有更新的点，如果这个点在绕负权环之前的话就是跳过这个点继续，如果这个点在环上的话就是重新换了个绕负权环的起点

注意

：该题是判断是否存在负环，并非判断是否存在从1开始的负环，因此需要将所有的点都加入队列中，更新周围的点

最后模拟一下初始化为0的超级源点法的大概过程
1. 构造一个虚拟节点 O，单向指向所有的节点，且到所有节点距离为0；
2. 新图是否有负环等价于原始的图。
3.dist数组一开始为0,没有违背算法过程，可以理解为根据算法已经从O 更新到了各个节点，接下来的代码就是顺理成章。所以dist数组从所有为0的状态开始是有对应意义的。就是先走一步。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
//dist 存的是当前从1号点到n号点的长度
//cnt 表示从1到x的最短路径中经过的点数
int dist[N], cnt[N];
bool st[N];

//邻接表就是数组模拟链表，图中每个节点拉出一条链，存储其所有邻边，e[i]表示邻边的另一个端点，w[i]表示邻边长度，ne[i]表示链表的下一个节点下标，idx表示当前用到第几个下标
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()
{
    queue<int> q;

    for (int i = 1; i <= n; i ++ )
    {
        st[i] = true;
        q.push(i);
    }

    while (q.size())
    {
        int t = q.front();
        q.pop();

        //及时修改状态
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;
                //如果j没有加入过队列再加入
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    if (spfa()) puts("Yes");
    else puts("No");

    return 0;
}