【图论】负环

知识点

---

负环，顾名思义，就是一张图上的一个边权和为负数的环。

负权边在最短路或此类问题上，会导致一些在正权图上能正常运行的算法失效。 

 处理负边权，可以采用Flody算法，Bellman-Ford算法，和优化过的Bellman-Ford算法：SPFA

 在竞赛中，大多数题目会卡SPFA算法，但碰到存在负边权的时候，SPFA算法就是正解了。

 SPFA算法核心代码：

queue <int> q;
inline bool SPFA()
{	
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(ans,0,sizeof(ans));
    //数组清零
	while(!q.empty()) q.pop(); //清空队列
	q.push(1); //先加入结点，然后记录
	dis[1]=0; //记录路径
	vis[1]=1; //统计该点已经搜索过
	while(!q.empty())
	{
		int u=q.front(); //取出队首元素
		vis[u]=0; //标记该点
		q.pop(); //弹出该点
		for(int i=head[u];i!=-1;i=edge[i].next) //链式前向星查找每个点的方式
		{
		int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w) //松弛操作
			{
				dis[v]=dis[u]+edge[i].w; 
				ans[v]=ans[u]+1; //统计已经走过的路径
				if(ans[v]>=n) //路径数大于n,存在点被第二次经过
				{
				return 1;		
				}
				if(!vis[v])  //如果到达的点不在队列里
				{	
				q.push(v); //将下一个点进队
				vis[v]=1;
				}
			}
		}
	}
	return 0;  //没有负环
}

---

 模板题：洛谷 P3385 【模板】负环

题目描述

给定一个 n 个点的有向图，请求出图中是否存在从顶点 1 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

输入格式

本题单测试点有多组测试数据。

输入的第一行是一个整数 T，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数 n 和接下来给出边信息的条数 m。

接下来 m 行，每行三个整数u,v,w。

• 若 w ≥ 0，则表示存在一条从 u 至 v 边权为 w 的边，还存在一条从 v 至 u 边权为 w 的边。
• 若 w < 0，则只表示存在一条从 u 至 v 边权为 w 的边。

输出格式

对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。

输入输出样例

输入 #1

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

输出 #1

NO
YES

说明/提示

数据规模与约定

对于全部的测试点，保证：

• 1≤n≤2×10^3，1≤m≤3×10^3。
• 1≤ u , v ≤n，−10^4≤w≤10^4。
• 1≤T≤10。

提示

请注意，m 不是图的边数。

---

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int t,n,m;
const int maxn=1e7+5,INF=0x3f3f3f3f;
struct node{
	int to,next,w;
}edge[maxn<<1];

int num=0,dis[maxn],head[maxn],ans[maxn];
bool vis[maxn];
queue <int> q;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void add(int u,int v,int w)
{
	edge[++num].to=v;
	edge[num].w=w;
	edge[num].next=head[u];
	head[u]=num;
}

inline void bellman_ford()
{	
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(ans,0,sizeof(ans));
    //数组清零
	while(!q.empty()) q.pop(); //清空队列
	q.push(1); //先加入结点，然后记录
	dis[1]=0; //记录路径
	vis[1]=1; //统计该点已经搜索过
	while(!q.empty())
	{
		int u=q.front(); //取出队首元素
		vis[u]=0; //标记该点
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
		int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w) //松弛操作
			{
				dis[v]=dis[u]+edge[i].w; 
				ans[v]=ans[u]+1; //统计已经走过的路径
				if(ans[v]>=n) //路径数大于n,存在点被第二次经过
				{
				printf("YES\n");
				return;		
				}
				if(!vis[v])  //如果到达的点不在队列里
				{	
				q.push(v); //将下一个点进队
				vis[v]=1;
				}
			}
		}
	}
	printf("NO\n");  //没有负环
}

int main()
{	
	t=read();
	for(int k=1;k<=t;++k)
	{
		n=read(); m=read();
		memset(head,-1,sizeof(head));
		for(int i=1;i<=m;++i)
		{
			int u=read(),v=read(),w=read();
			if(w>=0) 
			{
				add(u,v,w);
				add(v,u,w);
			}
			else add(u,v,w);
		}
		
		bellman_ford();
		
	}
	return 0;
}

---

相关练习：

1 . 洛谷 P2136 拉近距离

需要注意的细节：

1. 可以从1开始找，也可以从n开始找，即可以将图遍历两次。

2. 在遍历的过程中，只要有一次存在负环，就输出“Forever love”。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int n,m;
const int maxn=1e5+5,INF=0x3f3f3f3f;
struct node{
	int to,next,w;
}edge[maxn<<1];
int num=0,head[maxn],dis[maxn],ans[maxn];
bool vis[maxn];
queue <int> q;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

inline void add(int u,int v,int w)
{
	edge[++num].to=v;
	edge[num].w=w;
	edge[num].next=head[u];
	head[u]=num;
}

inline bool SPFA(int x)
{
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(ans,0,sizeof(ans));
	while(!q.empty()) q.pop();
	q.push(x);
	vis[x]=1;
	dis[x]=0;
	while(!q.empty())
	{
		int u=q.front();
		vis[u]=0;
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w)
			{
				dis[v]=dis[u]+edge[i].w;
				ans[v]=ans[u]+1;
				if(ans[v]>=n) 
				{
					return 1;
				}
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return 0;
}

int main()
{
	n=read(); m=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;++i)
	{
		int s=read(),t=read(),w=read();
		add(s,t,-w); //根据题目条件，路程会减小，路程取相反数
	}

	bool check=SPFA(1);
	int road=dis[n];
	bool check2=SPFA(n);
    //可以从1开始查找，也可以从n开始查找
	if(check == 1 || check2 == 1) printf("Forever love"); //只要有一边存在负环
	else write(min(dis[1],road));
	return 0;
}