题目：有一个图有N个顶点，M条边。边用三个整数a b w表示，意思为a->b有一条权值为w的边（若w<0则为单向，否则双向）。共T组数据。对于每组数据，存在负环则输出一行"YE5"(不含引号)，否则输出一行"N0"(不含引号)。
注意——坑爹的输出啊！！它不是平常的 YES 和 NO!!
解法：1.spfa_bfs，判断结点入队超过 n 次就出现负环。最差的情况是O(nm)。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std; const int N=;
struct edge{int x,y,d,next;}a[N*];
int last[N],vis[N],cnt[N],d[N];
int len,n,m;
queue<int> q; void ins(int x,int y,int d)
{
a[++len].x=x,a[len].y=y,a[len].d=d;
a[len].next=last[x],last[x]=len;
}
bool spfa()
{
while (!q.empty()) q.pop();
memset(d,,sizeof(d));
memset(cnt,,sizeof(cnt));
memset(vis,,sizeof(vis));
d[]=,vis[]=,cnt[]++;
q.push();
while (!q.empty())
{
int x=q.front();
q.pop(); vis[x]=;//此处无cnt++
for (int i=last[x];i!=-;i=a[i].next)
{
int y=a[i].y;
if (d[x]+a[i].d<d[y])
{
d[y]=d[x]+a[i].d;
if (!vis[y])
{
q.push(y);
vis[y]=, cnt[y]++;
if (cnt[y]>n) return true;
}
}
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&n,&m);
int x,y,d; len=;
memset(last,-,sizeof(last));
for (int i=;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&d);
ins(x,y,d);
if (d>=) ins(y,x,d);
}
if (spfa()) printf("YE5\n");
else printf("N0\n");
}
return ;
}
bfs TLE
2.spfa_dfs，枚举起点，找最短路，若再一次访问到已经访问过的结点就出现负环。最差的情况也是O(nm)。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; const int N=,INF=(int)1e9;
struct edge{int x,y,d,next;}a[N*];
int last[N],vis[N],dis[N];
int len,n,m; void ins(int x,int y,int d)
{
a[++len].x=x,a[len].y=y,a[len].d=d;
a[len].next=last[x],last[x]=len;
}
bool dfs(int x)
{
if (vis[x]) return true;
vis[x]=;
for (int i=last[x];i!=-;i=a[i].next)
{
int y=a[i].y;
//if (y==fa) continue;//有dis的判断
if (dis[x]+a[i].d<dis[y])
{
dis[y]=dis[x]+a[i].d;
if (dfs(y)) return true;
}
}
vis[x]=;//判断一个点是否在“同一”路径重复出现而已。
return false;//
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&n,&m);
int x,y,d; len=;
memset(last,-,sizeof(last));
for (int i=;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&d);
ins(x,y,d);
if (d>=) ins(y,x,d);
}
for (int i=;i<=n;i++) dis[i]=INF;
memset(vis,,sizeof(vis));
dis[]=;//起点不确定的！
if (dfs()) printf("YE5\n");
else printf("N0\n");
}
return ;
}
dfs WA（起点不能只是随便定一个点）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL; const int N=,D=;
const LL INF=(LL)5e10;
int n,m,len;
bool cir;
int last[N],vis[N];
LL dis[N];
struct edge{int x,y,next;LL d;}a[*N]; void ins(int x,int y,LL d)
{
a[++len].x=x,a[len].y=y,a[len].d=d;
a[len].next=last[x],last[x]=len;
}
void dfs(int x)
{
if (vis[x]) {cir=true;return;}
vis[x]=;
for (int i=last[x];i;i=a[i].next)
{
int y=a[i].y;
if (dis[x]+a[i].d<dis[y])
{
dis[y]=dis[x]+a[i].d;
dfs(y);
if (cir) return;
}
}
vis[x]=;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
int x,y; LL d;
len=;
memset(last,,sizeof(last));
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++)
{
scanf("%d%d%lld",&x,&y,&d);
ins(x,y,d);
if (d>=) ins(y,x,d);
}
cir=false;
for (int i=;i<=n;i++)
{
for (int j=;j<=n;j++) dis[j]=INF;
memset(vis,,sizeof(vis));
dis[i]=, dfs(i);
if (cir) break;
}
if (cir) printf("YE5\n");
else printf("N0\n");
}
return ;
}
dfs TLE
3.spfa_dfs+优化，既然是找负环，那么就是找权和为负数的回路。P.S.这个一定要理解！！ヾ(。￣□￣)ﾂ゜゜゜我想了很久......网上也没搜到。负环负环，不单单是含负权边的环，而是权和为负的环。原因是对于一个在负环里的点，只有经过负环后的距离还比原来的小，才会再一次访问该点。要不怎么会一直循环走这个环，直到RE呢......ヘ(_ _ヘ) 也就是环的权和为负数！
实现就是我们对 dis 数组清零，再权和为负的情况下做spfa，且使用 dfs 判断成环。时间复杂度远远小于O(nm)。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL; const int N=,D=;
const LL INF=(LL)5e10;
int n,m,len;
bool cir;
int last[N],vis[N];
LL dis[N];
struct edge{int x,y,next;LL d;}a[*N]; void ins(int x,int y,LL d)
{
a[++len].x=x,a[len].y=y,a[len].d=d;
a[len].next=last[x],last[x]=len;
}
void dfs(int x)
{
if (vis[x]) {cir=true;return;}
vis[x]=;
for (int i=last[x];i;i=a[i].next)
{
int y=a[i].y;
if (dis[x]+a[i].d<dis[y])
{
dis[y]=dis[x]+a[i].d;
dfs(y);
if (cir) return;
}
}
vis[x]=;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
int x,y; LL d;
len=;
memset(last,,sizeof(last));
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++)
{
scanf("%d%d%lld",&x,&y,&d);
ins(x,y,d);
if (d>=) ins(y,x,d);
}
memset(dis,,sizeof(dis));
memset(vis,,sizeof(vis));
cir=false;
for (int i=;i<=n;i++)
{
dfs(i);
if (cir) break;
}
if (cir) printf("YE5\n");
else printf("N0\n");
}
return ;
}
dfs AC