【定义与概念】
给定一张有向图，若其中存在一个环的所有权值之和为负数，这个环称为负环。
【算法实现】
当然，负环的求解可以暴搜，但是时间复杂度就难以入眼了，我们回到求解单源最短路径算法上面，看看它们能否求解。
我们知道
| 算法名称 | 能否处理负边 | 时间复杂度 |
| Dijkstra | 不能，负权的存在使得最短路径不一定最短 | O(n^2) |
| 堆优化Dijkstra | 不能，如上 | O(mlogn) |
| Bellman-Ford | 能 | O(nm) |
| SPFA | 能 | O(km) |
我们主要使用SPFA，讲一下SPFA判断负环。
SPFA有三种以上的方法判断负环：
- 设cnt[x]表示1~x的最短路径包含边数，cnt[1]=0。当收敛边权（判断三角形不等式）时，更新cnt[y]=cnt[x]+1。如果某时cnt[x]>=边的总数m，说明存在负环。
- 记录每个点入队的次数，如果某个点入队次数超过点的总数n，说明存在最小环。
- 卡时判负环，判负环最骚的操作。给队列总长度做限制，超过限制说明有环。至于这个限制具体是什么，请去问玄学，我不知道。
给出第一、二种解法的参考吧。
拿道板子题出来。
P3385 【模板】负环
注意这道题鬼畜的输出。。。
这是第一种： 573ms / 5.04MB AC
#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstring>
#include<vector>
#include<ctime>
#define N 10010
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int head[N],tot,n,m,d[N],cnt[N];
struct rec{
int next,ver,edge;
}g[N<<];
void add(int x,int y,int val){
g[++tot].ver=y,g[tot].edge=val;
g[tot].next=head[x],head[x]=tot;
}
bool spfa(int x)
{
memset(d,0x3f,sizeof(d));
memset(cnt,,sizeof(cnt));
d[x]=;cnt[x]=;
q.push(x);
while(q.size())
{
int index=q.top();q.pop();
for(int i=head[index];i;i=g[i].next){
int y=g[i].ver,z=g[i].edge;
if(d[y]>d[index]+z){
d[y]=d[index]+z;
cnt[y]=cnt[index]+;
if(cnt[y]>=m) return ;
q.push(y);
}
}
}
return ;
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(g,,sizeof(g));
memset(head,,sizeof(head));
if(!q.empty()) q.pop();
tot=;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int x,y,val;
scanf("%d%d%d",&x,&y,&val);
if(val<) add(x,y,val);
else add(x,y,val),add(y,x,val);
}
if(spfa()) cout<<"YE5"<<endl;
else cout<<"N0"<<endl;
}
return ;
}
这是第二种：1965ms / 9.04MB 91pnts
#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 10010
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int head[N],tot,n,m,d[N],cnt[N];
struct rec{
int next,ver,edge;
}g[N<<];
void add(int x,int y,int val){
g[++tot].ver=y,g[tot].edge=val;
g[tot].next=head[x],head[x]=tot;
}
bool spfa(int x)
{
memset(v,,sizeof(v));
memset(d,0x3f,sizeof(d));
memset(cnt,,sizeof(cnt));
d[x]=;cnt[x]=;
q.push(x);
while(q.size())
{
int index=q.top();q.pop();
for(int i=head[index];i;i=g[i].next){
int y=g[i].ver,z=g[i].edge;
if(d[y]>d[index]+z){
d[y]=d[index]+z;
if(cnt[y]>=n) return ;
cnt[y]++,q.push(y),v[y]=;
}
}
}
return ;
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(g,,sizeof(g));
memset(head,,sizeof(head));
if(!q.empty()) q.pop();
tot=;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int x,y,val;
scanf("%d%d%d",&x,&y,&val);
if(val<) add(x,y,val);
else add(x,y,val),add(y,x,val);
}
if(spfa()) cout<<"YE5"<<endl;
else cout<<"N0"<<endl;
}
return ;
}