Bellman_ford和Spfa判断负环

# 判断负环
### 最短路在某些时候是没有最短路，在整张图中有边权之和为负数的环时，没有最短路
### 知周所众，bellman_ford跑n-1次必定求出最短路，但如果有负环,第n次依然会有更新，只需特判就可求出是否有有负环
### spfa也是用来求负权边最短路的，它也能判负环吗？
### 答案是肯定的，一张未带负环的图，最多n-1条边，但是如果有负环，可以被无限更新，最短路的边数也会多于n-1条，因此，我们可以用spfa来判断负环，而且很不会被卡
## [P3385 【模板】负环](https://www.luogu.com.cn/problem/P3385)
### 这题就是典型负环题，但bellman_ford不能用，因为这题是判断从1能到的负环，而bellman_ford只能判整张图上的负环
```cpp
#include <bits/stdc++.h>
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
queue<int> q;
vector<PII> v[N];
int t[N],t1[N];
bool b[N];
int n,m;
void f(){
	for(int i=1;i<=n;i++) v[i].clear();
	while(!q.empty()) q.pop();
	memset(t1,0,sizeof t1);
	memset(b,0,sizeof b);
}
bool spfa(int x){
	memset(t,0x3f,sizeof t);
	t[x]=0;
	q.push(x);
	b[x]=1;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		b[k]=0;
		for(int i=0;i<v[k].size();i++){
			int k1=v[k][i].x,k2=v[k][i].y;
			if(t[k1]>t[k]+k2){
				t[k1]=t[k]+k2;
				t1[k1]=t1[k]+1;
				if(t1[k1]>=n) return 1;
				if(!b[k1]){
					q.push(k1);
					b[k1]=1;
				}
			}
		}
	}
	return 0;
}
signed main(){
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m;
		f();
		for(int i=1;i<=m;i++){
			int x,y,z;
			cin>>x>>y>>z;
			v[x].push_back({y,z});
			if(z>=0) v[y].push_back({x,z});
		}
		if(spfa(1)) puts("YES");
		else puts("NO");
	}
	return 0;
}
```
## [P1938 [USACO09NOV] Job Hunt S](https://www.luogu.com.cn/problem/P1938)
### 这题是求最长路，让我们判断有无正环
### 代码：
```cpp
#include <bits/stdc++.h>
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
queue<int> q;
vector<PII> v[N];
int t[N],t1[N];
bool b[N];
int n,m1,m2,k,d;
bool spfa(int x){
	memset(t,-0x3f,sizeof t);
	t[x]=d;
	q.push(x);
	b[x]=1;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		b[k]=0;
		for(int i=0;i<v[k].size();i++){
			int k1=v[k][i].x,k2=v[k][i].y;
			if(t[k1]<t[k]+k2){
				t[k1]=t[k]+k2;
				t1[k1]=t1[k]+1;
				if(t1[k1]>=n) return 1;
				if(!b[k1]){
					q.push(k1);
					b[k1]=1;
				}
			}
		}
	}
	return 0;
}
signed main(){
	cin>>d>>m1>>n>>m2>>k;
	for(int i=1;i<=m1;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back({y,d});
	}
	for(int i=1;i<=m2;i++){
		int x,y,z;
		cin>>x>>y>>z;
		v[x].push_back({y,d-z});
	}
	int k1=spfa(k);
	if(k1) puts("-1");
	else{
		int s=INT_MIN;
		for(int i=1;i<=n;i++) s=max(s,t[i]);
		cout<<s<<endl;
	}
	return 0;
}
```
## 总结：
### bellman_ford只能判断整张图的负环，而spfa可以判断任意要求负环，而spfa判断负环也不会被卡

正在渲染内容...