[模板]poj3259(判断是否存在负环)

2017年07月12日 7点热度 0人点赞 0条评论
Wormholes
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 51623   Accepted: 19175

Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms
comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..NM (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000
seconds.

Input

Line 1: A single integer, FF farm descriptions follow. 
Line 1 of each farm: Three space-separated integers respectively: NM, and W 
Lines 2..M+1 of each farm: Three space-separated numbers (SET) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected
by more than one path. 
Lines M+2..M+W+1 of each farm: Three space-separated numbers (SET) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.

Output

Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

Sample Input

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

Sample Output

NO

YES

bellman-ford负环,如果每个边都松弛了n-1还能松弛,则有负环,效率低

判断给定的有向图中是否存在负环。

      利用 spfa 算法判断负环有两种方法:

      1 spfa  dfs 形式,判断条件是存在一点在一条路径上出现多次。

      2 spfa  bfs 形式,判断条件是存在一点入队次数大于总顶点数。

DFS

spfa的SLF优化:SLF:Small LabelFirst 策略,设要加入的节点是j,队首元素为i,若dist(j)

 

//注意一开始的图是双向的 
//bellman-ford判负环
//时间复杂度分析:log(n*m) 
//通过本次wa,我明白了cin的执行顺序是从右到左的 
//此代码效率莫名的高,可能是操作简单吧 
#include
#include
#include
using namespace std;
const int mn=502,mm=5300;
int n,m,ww,tot;
int u[mm],v[mm],w[mm];
int dis[mn];
bool bellman_ford()
{
	for(int i=1;i<=n;i++) dis[i]=499999999;
	dis[1]=0;
	for(int i=1;idis[u[i]]+w[i])
		{
			dis[v[i]]=dis[u[i]]+w[i];
			f=0;
		}
		if(f) return false;
	}
	for(int i=0;idis[u[i]]+w[i]) return true;
	return false;
}
int main(){
	ios::sync_with_stdio(0);
	int T;
	cin>>T;
	while(T--)
	{
	cin>>n>>m>>ww;
		tot=0;
		while(m--)
		{
		cin>>u[tot]>>v[tot]>>w[tot];
		tot++;
		v[tot]=u[tot-1],u[tot]=v[tot-1],w[tot]=w[tot-1];
		tot++;
		}
		while(ww--)
		{
			cin>>u[tot]>>v[tot]>>w[tot];
			w[tot]=-w[tot];
			tot++;
		}
		if(bellman_ford()) cout<<"YESn";
		else cout<<"NOn";
	}
	return 0;
}

//spfa判负环dfs,不推荐(效率低)
#include
#include
#include
#include
using namespace std;
const int mn=502,mm=5300;
struct node{
	int to,w,next;
}edge[mm];
int n,m,ww,tot;
int dis[mn],vis[mn],head[mn];
void add(int u,int v,int w)
{
	edge[tot].to=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot++;
}
bool spfa(int u)
{
	for(int i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(dis[v]>dis[u]+edge[i].w)
		{
			if(vis[v]) return true;
			vis[v]=1;
			dis[v]=dis[u]+edge[i].w;
			if(spfa(v)) return true;
			vis[v]=0;
		}
	}
	return false;
}
int main()
{
	int u,v,w;
	int T;
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--)
	{
		tot=0;
		cin>>n>>m>>ww;
		memset(head,-1,sizeof(head));
		for(int i=0;i>u>>v>>w;
			add(u,v,w);
			add(v,u,w);
		}
		for(int i=0;i>u>>v>>w;
			add(u,v,-w);
		}
		for(int i=1;i<=n;i++) dis[i]=49999999;
		dis[1]=0;
		memset(vis,0,sizeof(vis));
		vis[1]=1;
		if(spfa(1)) cout<<"YESn";
		else cout<<"NOn";
	}
	return 0;
}

//spfa判负环bfs,时间复杂度ke,e为边数,k为入队列次数
#include
#include
#include
#include
using namespace std;
const int mn=502,mm=5300;
struct node{
	int to,w,next;
}edge[mm];
int n,m,ww,tot;
int dis[mn],inq[mn],head[mn],cnt[mn];
void add(int u,int v,int w)
{
	edge[tot].to=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot++;
}
bool spfa()
{
	for(int i=1;i<=n;i++) dis[i]=49999999;
	memset(cnt,0,sizeof(cnt));
	memset(inq,0,sizeof(inq));
	dis[1]=0,inq[1]=cnt[1]=1;;
	queue q;
	q.push(1);
	while(q.size())
	{
		int x=q.front();
		q.pop();
		inq[x]=0;
		for(int i=head[x];i!=-1;i=edge[i].next)
		{
			int u=edge[i].to;
			if(dis[u]>dis[x]+edge[i].w)
			{
				dis[u]=dis[x]+edge[i].w;
				if(!inq[u])
				{
					if(++cnt[u]>=n) return true;
					inq[u]=1;
					q.push(u);
				}
			}
		}
	}
	return false;
}
int main()
{
	int u,v,w;
	int T;
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--)
	{
		tot=0;
		cin>>n>>m>>ww;
		memset(head,-1,sizeof(head));
		for(int i=0;i>u>>v>>w;
			add(u,v,w);
			add(v,u,w);
		}
		for(int i=0;i>u>>v>>w;
			add(u,v,-w);
		}
		if(spfa()) cout<<"YESn";
		else cout<<"NOn";
	}
	return 0;
}
//spfa判负环bfs+slf优化 
#include
#include
#include
#include
using namespace std;
const int mn=502,mm=5300;
struct node{
	int to,w,next;
}edge[mm];
int n,m,ww,tot;
int dis[mn],inq[mn],head[mn],cnt[mn];
void add(int u,int v,int w)
{
	edge[tot].to=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot++;
}
bool spfa()
{
	for(int i=1;i<=n;i++) dis[i]=49999999;
	memset(cnt,0,sizeof(cnt));
	memset(inq,0,sizeof(inq));
	dis[1]=0,inq[1]=cnt[1]=1;;
	deque q;
	q.push_back(1);
	while(q.size())
	{
		int x=q.front();
		q.pop_front();
		inq[x]=0;
		for(int i=head[x];i!=-1;i=edge[i].next)
		{
			int u=edge[i].to;
			if(dis[u]>dis[x]+edge[i].w)
			{
				dis[u]=dis[x]+edge[i].w;
				if(!inq[u])
				{
					if(++cnt[u]>=n) return true;
					inq[u]=1;
					if(q.size()&&dis[q.front()]>dis[u])
					q.push_front(u);
					else q.push_back(u);
				}
			}
		}
	}
	return false;
}
int main()
{
	int u,v,w;
	int T;
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--)
	{
		tot=0;
		cin>>n>>m>>ww;
		memset(head,-1,sizeof(head));
		for(int i=0;i>u>>v>>w;
			add(u,v,w);
			add(v,u,w);
		}
		for(int i=0;i>u>>v>>w;
			add(u,v,-w);
		}
		if(spfa()) cout<<"YESn";
		else cout<<"NOn";
	}
	return 0;
}

未经允许不得转载![模板]poj3259(判断是否存在负环)

update

纸上得来终觉浅, 绝知此事须躬行。