POJ 3259 Wormholes 邻接表的SPFA判断负权回路

http://poj.org/problem?id=3259

题目大意:

一个农民有农场,上面有一些虫洞和路,走虫洞可以回到 T秒前,而路就和平常的一样啦,需要花费时间走过。问该农民可不可能从某个点出发后回到该点,并且于出发时间之前?


思路:

就是让我们判断存不存在一条总权值未负的回路。

你想想,如果我们一直走这个回路,就可以无限的回到过去。( (╯‵□′)╯︵┻━┻世上哪有时空隧道。想回到过去么?如果可以? 你会去做什么,挽回让自己后悔的事情? ,咳咳,继续题解。)

那就用SPFA呗,如果一个点入队次数超过n,那么就存在回路。(因为SPFA求最短路,如果存在环,那么会一直入队。。出。。,也就是说环的是没有最小值的,而正环只会走一次。)

SPFA常见的优化有SLF和LLL

SLF是指在入队时如果当前点的dist值小于队首, 则插入到队首, 否则插入到队尾。



未优化的版本:

157MS

#include<cstdio>
#include<string>
#include<queue>
using namespace std;
const int INF=9999999;
const int MAXN=520;
const int MAXM=5200;
struct edge
{
	int to;
	int val;
	int next;
}e[MAXM];
int len,head[MAXN];
int dis[MAXN];
int n,m,w;
bool SPFA()
{
	for(int i=1;i<=n;i++)
		dis[i]=INF;

	bool vis[MAXN]={0};
	int cnt[MAXN]={0};

	int cur=1;

	queue<int> q;
	q.push(cur);
	vis[cur]=true;
	cnt[cur]=1;
	dis[cur]=0;

	while(!q.empty())
	{
		cur=q.front();
		q.pop();
		vis[cur]=false;
		if(cnt[cur]>n)
			return true;


		for(int i=head[cur]  ;i!=-1; i=e[i].next)
		{
			int id=e[i].to;
			if( dis[cur] + e[i].val < dis[ id ] )
			{
				dis[ id ] = dis[cur] + e[ i ].val;
				if(!vis[id])
				{
					cnt[id]++;
					vis[id]=true;
					q.push(id);
				}
			}
		}
	}
	return false;
}

void add(int from,int to,int val)
{
	e[len].to=to;
	e[len].val=val;
	e[len].next= head[from];
	head[from]=len++;
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(head,-1,sizeof(head));
		len=0;

		scanf("%d%d%d",&n,&m,&w);
		for(int i=0;i<m;i++)
		{
			int from,to,val;
			scanf("%d%d%d",&from,&to,&val);
			add(from,to,val);
			add(to,from,val); //双向的
		}
		for(int i=0;i<w;i++)
		{
			int from,to,val;
			scanf("%d%d%d",&from,&to,&val);
			add(from,to,-val);
		}
		if( SPFA())
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}


采用优化的版本:

63MS

#include<cstdio>
#include<string>
#include<queue>
using namespace std;
const int INF=9999999;
const int MAXN=520;
const int MAXM=5200;
struct edge
{
	int to;
	int val;
	int next;
}e[MAXM];
int len,head[MAXN];
int dis[MAXN];
int n,m,w;
bool SPFA()
{
	for(int i=1;i<=n;i++)
		dis[i]=INF;

	bool vis[MAXN]={0};
	int cnt[MAXN]={0};

	int cur=1;

	deque<int> q;
	q.push_back(cur);
	vis[cur]=true;
	cnt[cur]=1;
	dis[cur]=0;

	while(!q.empty())
	{
		cur=q.front();
		q.pop_front();
		vis[cur]=false;
		if(cnt[cur]>n)
			return true;


		for(int i=head[cur]  ;i!=-1; i=e[i].next)
		{
			int id=e[i].to;
			if( dis[cur] + e[i].val < dis[ id ] )
			{
				dis[ id ] = dis[cur] + e[ i ].val;
				if(!vis[id])
				{
					cnt[id]++;
					vis[id]=true;				
					if(!q.empty() && dis[id] < dis[q.front()])
						q.push_front(id);
					else
						q.push_back(id);
				}
			}
		}
	}
	return false;
}

void add(int from,int to,int val)
{
	e[len].to=to;
	e[len].val=val;
	e[len].next= head[from];
	head[from]=len++;
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(head,-1,sizeof(head));
		len=0;

		scanf("%d%d%d",&n,&m,&w);
		for(int i=0;i<m;i++)
		{
			int from,to,val;
			scanf("%d%d%d",&from,&to,&val);
			add(from,to,val);
			add(to,from,val); //双向的
		}
		for(int i=0;i<w;i++)
		{
			int from,to,val;
			scanf("%d%d%d",&from,&to,&val);
			add(from,to,-val);
		}
		if( SPFA())
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}


POJ 3259 Wormholes 邻接表的SPFA判断负权回路

上一篇:服务器编程入门(1)TCP/IP协议族


下一篇:浅淡传统企业进入移动互联网的几种方式