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");
}