程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1317 XYZZY(spfa判環)

hdu 1317 XYZZY(spfa判環)

編輯：C++入門知識

http://acm.hdu.edu.cn/showproblem.php?pid=1317

大致題意：有n個房間，每個房間都有對應的能量值（可正可負），現在從1出發要到達n，初始能量為100，問是否能夠達到n點，到達n的條件是中間及最後的能量值都要大於0.

思路：若不考慮環，那麼求最長路判斷是否大於0即可。若存在負環，對求最長路也沒影響；但當存在正環時，最長路就不存在了。可用spfa判斷，當某點入隊超過n次，那麼它必定在環中，直接將其dis置為INF，並不再將其近隊列。最後若能到達n則可行，否則失敗。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 110;

int n;
int dis[maxn];
int inque[maxn];
int out[maxn];
vector  edge[maxn];
int w[maxn];

bool spfa()
{
	queue  que;
	memset(dis,-INF,sizeof(dis));
	memset(inque,0,sizeof(inque));
	memset(out,0,sizeof(out));

	inque[1] = 1;
	dis[1] = 100;
	que.push(1);

	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		inque[u] = 0;
		out[u]++;

		if(out[u] > n) //在環中不再僅隊列
			continue;
		if(out[u] == n) //將dis置為INF
			dis[u] = INF;

		for(int i = 0; i < (int)edge[u].size(); i++)
		{
			int v = edge[u][i];
			if(dis[v] < dis[u] + w[v] && dis[u] + w[v] > 0)//注意中間也要保證>0
			{
				dis[v] = dis[u] + w[v];
				if(v == n) //能夠到達n返回true
					return true;
				if(!inque[v])
				{
					inque[v] = 1;
					que.push(v);
				}
			}
		}
	}
	return false;
}

int main()
{
	int num,v;
	while(~scanf("%d",&n))
	{
		if(n == -1) break;

		for(int i = 1; i <= n; i++)
		{
			edge[i].clear();
			scanf("%d",&w[i]);
			scanf("%d",&num);
			while(num--)
			{
				scanf("%d",&v);
				edge[i].push_back(v);
			}
		}

		if(spfa())
			printf("winnable\n");
		else printf("hopeless\n");
	}
	return 0;
}