spfa判断负环有两种方式:1)某个点入队n次 2)某个点的最短路包含边数≥n(额外使用一个cnt数组记录每个点的最短路边数,在这个点被临点松弛操作后+1) 抽屉原理
spfa可以求负环也可以求正环,属于对偶问题。求负环的时候时最短路,求正环改成最长路即可,因为最短路才能在负环上一直转同理正环。只需要改变松弛操作的不等号方向
在算法的最开始要利用超级源点的思想把所有点都加入队列,因为起点可能不在环上,或者这个环是孤立的
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=2010,M=10010;
int idx,n,m;
int ne[M],e[M],w[M],h[N];
int dist[N],cnt[N];
bool st[N];
void add(int a,int b,int c){
w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(){
queue<int> q;
for(int i=1;i<=n;i++){
q.push(i);
st[i]=true;
}
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];~i;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(!st[j]){
q.push(j);
st[j]=true;
}
if(cnt[j]>=n) return true;
}
}
}
return false;
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}