聊聊判断负环效率
查看原帖
聊聊判断负环效率
93041
__Watcher楼主2020/6/22 07:55

Rt,对于第 10 个点,如下代码会 TLE:

while(l!=r){
		u=q[l], l++;
		if(l==N) l=0;
		vis[u]=0;
		if(++cnt[u]>=n) {
			cout<<"No";
			return 0; 
		}
		for(register int k=h[u];k;k=d[k].n){
			v=d[k].b, c=d[k].c;
			if(t[u]+c<t[v]&&!vis[v]){
				t[v]=t[u]+c;
				vis[v]=1;
				q[r++]=v;
				if(r==N) r=0;
			}
		}
	}

如下代码能 AC :

while(l!=r){
		u=q[l], l++;
		if(l==N) l=0;
		vis[u]=0;
		for(register int k=h[u];k;k=d[k].n){
			v=d[k].b, c=d[k].c;
			if(t[u]+c<t[v]&&!vis[v]){
			    cnt[v]=max(cnt[v], cnt[u]+1);
			    if(cnt[v]>n) {
			        cout<<"No";
			        return 0;
			    }
				t[v]=t[u]+c;
				vis[v]=1;
				q[r++]=v;
				if(r==N) r=0;
			}
		}
	}

而查看提交记录,dfs_spfa 快的飞起。请问第二种负环判断方式是否正确?而 dfs_spfa 是否实用?望解答,谢谢啦。

2020/6/22 07:55
加载中...