【学习笔记】负环

负环

定义：给定一张有向图（无向图可以看作有向图），每条边有一个权值。若一条边的权值为负数，则称它为负边权。若图中存在一个环，环上的各边权之和为负数，则称这个环为“负环”。

——\(from\)《算法竞赛进阶指南》

而处理负边权我们就可以使用\(SPFA\)了

设\(cnt[x]\)表示从1到x的最短路径包含的边数，\(cnt[1]=0\)，当我们更新\(d[y]=d[x]+z\)时，同时更新\(cnt[y]=cnt[x]+1\)

若\(cnt[y]>=n\)，则有负环，假设没有负环的情况，一共有\(n\)个点，则最短路最多经过\(n\)个点，\(n-1\)条边，一个点过2次，不是最优解

负环代码

洛谷【模板】负环

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=2e5+5;
queue q;
bool v[N];
int ver[N],tot,head[N],cnt[N],nxt[N],d[N],edge[N],n,m,t;
inline int read(){
  int x=0,f=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}
inline void add(int x,int y,int z){
  ver[++tot]=y,nxt[tot]=head[x],head[x]=tot,edge[tot]=z;
}
inline void spfa(){
  memset(d,0x3f,sizeof(d));
  memset(v,0,sizeof(v));
  memset(cnt,0,sizeof(cnt));
  while(q.size())q.pop();
  d[1]=0;v[1]=1;q.push(1);
  while(q.size()){
    int x=q.front();v[x]=0;q.pop();
    for(int i=head[x];i;i=nxt[i]){
      int y=ver[i],z=edge[i];
      if(d[y]>d[x]+z){
	d[y]=d[x]+z;
	cnt[y]=cnt[x]+1;
	if(cnt[y]>=n){
	  cout<<"YES"<=0) add(u,v,w),add(v,u,w);
      else add(u,v,w);
    }
    spfa();
  }
  return 0;
}