首页 > 代码库 > vijos1053 用spfa判断是否存在负环

vijos1053 用spfa判断是否存在负环

2024-07-17 05:05:35   224人阅读

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;}

 

= =第六个点WA得我好不爽....但是又懒得改╮(╯▽╰)╭好像很纠结？


联系
我们