POJ 1932 XYZZY (ZOJ 1935)SPFA+floyd

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

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1935


题目大意:

看到XYZZY可不要以为是在玩扫雷哦。

给你一张图,初始你在房间1,初始生命值为100,进入每个房间会加上那个房间的生命(可能为负),要你进入房间n,问是否可能。(要求进入每个房间后生命值都大于0)

思路:

1、SPFA求最长路径,如果路径存在(即无环),那么肯定可以。

2、存在负环,不管她,因为如果为负,那就失败了。

3、存在正环,那么说明有无限生命((╯‵□′)╯︵┻━┻ 开挂啊,快举报!),不过无限生命也要求你可达n(我WA了就是因为这个!)

那么如何判断存在环?

用SPFA中,如果一个点入队超过n次,说明存在环。 - -|||


#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF=-9999999;
const int MAXN=111;//注孤 - -|||
bool map[MAXN][MAXN];
int val[MAXN],dis[MAXN];
int n;
bool SPFA()
{
	for(int i=1;i<=n;i++)
		dis[i]=INF;

	bool vis[MAXN]={0};

	int cnt[MAXN]={0};
	
	queue<int> q;
	q.push(1);
	vis[1]=true;
	dis[1]=100;
	cnt[1]=1;

	while(!q.empty())
	{
		int cur=q.front();
		q.pop();
		if(cnt[cur] > n)
			break;

		for(int i=1;i<=n;i++)
		{
			if(map[cur][i]==true && dis[cur] + val[i] > dis[i]
			&& dis[cur] + val[i] > 0 )
			{
				dis[i]=dis[cur] + val[i];
				if(!vis[i])
				{
					q.push(i);
					vis[i]=true;
					cnt[i]++;
				}
			}		
		}
		vis[cur]=false;
	}

	if(dis[n]>0)
		return true;
	else 
	{
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if(map[i][k] && map[k][j])
						map[i][j]=true;

		for(int i=1;i<=n;i++)
			if(cnt[i]>n && map[1][i] && map[i][n]) //忘记要从i到N了
				return true;
		return false;
	}
}

int main()
{
	while(~scanf("%d",&n),n!=-1)
	{
		memset(map,0,sizeof(map));
		memset(val,0,sizeof(val));

		for(int i=1;i<=n;i++)
		{
			int cnt,temp;
			scanf("%d %d",&val[i],&cnt);
			for(int j=1;j<=cnt;j++)
			{
				scanf("%d",&temp);
				map[i][temp]=true;
			}
		}

		if(SPFA())
			puts("winnable");
		else
			puts("hopeless");

	}
	return 0;
}


POJ 1932 XYZZY (ZOJ 1935)SPFA+floyd

上一篇:NSBezierPath 赛贝尔曲线画聊天泡泡


下一篇:Solidwork软件(license)许可证竟然还可以这样用!