spfa判负环

我们可以在原来的基础上多加一个cnt数组，表示这个点与前面的点一共被更新了多少次
就是cnt[j]=cnt[t]+1
如果当前的cnt某个数大于等于n，说明他肯定被更新超过了两次（鸽巢原理），那么就是负环了
但是还有一些特殊情况，比如点1与某些点不连通，但是那些点却构成了负环，所以我们的spfa队列一开始不能只从1开始，而是所有数。如果他是负环，在一定次数的循环后他的cnt还是会大于等于n。

所以只需要将spfa最短路改一下就好了：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
vector<int> v[N],w[N];
int dist[N];
int n,m;
bool st[N];
int cnt[N];
bool spfa()
{//因为我们并不是要求最短路，所以可以不需要初始化，如果是负环他肯定可以更新，因为加上负数会小于0，就能更新，如果边权是正数更新则毫无意义
    queue<int> q;
    for(int i=1;i<=n;i++) q.push(i),st[i]=true;//st数组全部标记
    while(!q.empty())
    {
        int f=q.front();
        q.pop();
        st[f]=false;
        int tt=v[f].size();
        for(int i=0;i<tt;i++)
        {
            int tmp=v[f][i];

            if(dist[tmp]>dist[f]+w[f][i])
            {
                cnt[v[f][i]]=cnt[f]+1;
                if(cnt[v[f][i]]>=n) return true;
                dist[tmp]=dist[f]+w[f][i];
                if(!st[tmp])
                {
                    q.push(tmp);
                    st[tmp]=true;
                }
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back(y);
        w[x].push_back(z);
    }
    if(spfa()) puts("Yes");
    else puts("No");
}