[模板]SPFA判负环

目录

• 一、BFS法判负环
• 二、DFS法判负环
• 三、SPFA判正环

---

一、BFS法判负环

Code：

#include<bits/stdc++.h>

#define re register

#define INF 0x3f3f3f3f

using namespace std;

int n,m;

int first[8000],next[8000],go[8000],tot,cost[8000];

int dist[8000],vis[8000],add[8000];

inline void add_edge(int u,int v,int w){

	next[++tot]=first[u];

	first[u]=tot;

	go[tot]=v;cost[tot]=w;

}

inline void read(int &x){

	x=0;int flag=1;char ch=getchar();

	while(isdigit(ch)){if(ch=='-') flag=-1;ch=getchar();}

	while(!isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

	x*=flag;

}

int SPFA(){

	queue<int> q;

	for(int i=1;i<=n;i++){dist[i]=INF;vis[i]=0;}

	dist[1]=0;vis[1]=1;q.push(1);

	while(!q.empty()){

		int u=q.front();

		q.pop();vis[u]=0;

		for(int e=first[u];e;e=next[e]){

			int v=go[e],w=cost[e];

			if(dist[v]>dist[u]+w){

				dist[v]=dist[u]+w;

				add[v]++;				//核心代码

				if(add[v]>n) return 1;

				if(!vis[v]){

					vis[v]=1;

					q.push(v);

				}

			}

		}

	}

	return 0;

}

int main()

{

	read(n),read(m);

	for(re int i=1;i<=m;i++){

		int u,v,w;

		read(u),read(v),read(w);

		add_edge(u,v,w);

	}

	if(SPFA()) printf("YES\n");

	else printf("NO\n");

	return 0;

}

二、DFS法判负环

给出主体部分，其余部分与上一个代码类似。

Code：

int SPFA(int u)

{

	vis[u]=1;

	for(int i=first[u];i;i=next[i])

	{

		int v=go[i],w=cost[i];

		if(dist[v]>dist[u]+w)

		{

			dist[v]=dist[u]+w;

			if(vis[v]||SPFA(v)){

				vis[v]=0;

				return 1;

			}

		}

	}

	vis[u]=0;

	return 0;

}

三、SPFA判正环

1. 由原来的最短路改为最长路
2. 将权值变为原来的相反数并跑最短路判负环

---