MARK 用spfa判断是否存在负环
判断是否存在负环的方法有很多,
其中用spfa判断的方法是:如果存在一个点入栈两次,那么就存在负环。
细节想想确实是这样,按理来说是不存在入栈两次的如果边权值为正的话
这个算法是O(N*M)
还有一种方法是直接用bellman-ford,虽说spfa也就是bellman-ford+FIFO队列
而且bellman-ford还可以计算负环的值
顺手附上代码好了:
for(int i=0;i<n;i++) d[i]=INF;//初始化
d[0]=0; for(int k=0;k<n-1;k++)//迭代n-1次,目前不懂为什么
for(int i=0;i<m;i++){//检查每条边
int x=u[i],y=v[i];
if(d[x]<INF) d[y]<?=d[x]+w[i];
}
这一题我是没有用bellman-ford...因为看到有人说用这个超时了= =
这里说一下用spfa的做法= =
虽然本蒟蒻第6个点莫名WA,但是毕竟思路还是正确的,自己MARK一下
目测是一些地方没有考虑到吧,据说有重边?有可能是这个?= =懒得管了
其实就是每个点都spfa一遍,看是否存在负环;
如果不存在的的话,就输出s-这些点的距离
至于spfa里面,其实也很简单,就是
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].to;
if(dist[v]>dist[u]+e[i].w){
dist[v]=dist[u]+e[i].w;
if(!vis[v]){
vis[v]=true;
q.push(v);
if(ans[v]<2){//这里用数组ans记录下,v这个点入栈几次
ans[v]++;
}
else return true;
}
}
}
}
附上完整代码:
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
const int maxn=101000;
int n,m,k,t,x,y,s,z,tot=0;
struct edge{
int from,to,w,next;
}e[1010000];
int head[maxn],dist[maxn],ans[maxn];
bool vis[maxn];
int f[maxn];
bool flag;
void add(int x,int y,int z){
e[tot].from=x;
e[tot].to=y;
e[tot].w=z;
e[tot].next=head[x];
head[x]=tot++;
}
bool spfa(int s){
queue<int>q;
memset(dist,63,sizeof(dist));
memset(vis,false,sizeof(vis));
memset(ans,0,sizeof(ans));
q.push(s);
dist[s]=0;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].to;
if(dist[v]>dist[u]+e[i].w){
dist[v]=dist[u]+e[i].w;
if(!vis[v]){
vis[v]=true;
q.push(v);
if(ans[v]<2){
ans[v]++;
}
else return true;
}
}
}
}
return false;
}
int main(){
freopen("data.txt","r",stdin);
scanf("%d%d%d",&n,&m,&s);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
if(x==y && z<0){
printf("-1\n");
return 0;
}
}
for(int i=1;i<=n;i++){
if(spfa(i)){
printf("-1\n");
return 0;
}
}
spfa(s);
for(int i=1;i<=n;i++){
if(dist[i]>1000000){
if(i!=s) printf("NoPath\n");
else printf("0\n");
}
else printf("%d\n",dist[i]);
}
return 0;
}