HDU-1317 XYZZY 题解

题目大意

有n个房间，你的初始能量是100，你需要从第一个房间到达第n个房间，每个房间的能量为-100~+100之间，你每走进一个房间，你就会加上这个房间的能量，如果能量小于0就失败了。问你能否到达第n个房间。

解题思路

这个图是一个有向图。首先可以用Floyd判能否达到，如果不能到达，那么肯定不行。

由于这个图存在正环的情况，所以需要Spfa去处理。如果存在正环，那么只用判断是否能从正环中到达n点，如果能够到达，那必定可以，否则不行。

其他情况只用判断从1到n点的最长路是否大于0，大于0的话就可以到达，否则不行。

（Spfa初体验。。应该算是Spfa的模板题了吧

感觉Spfa比Bellman-Ford要简单一点

完整代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int energy[110], vis[110], road[110][110], power[110],out[110],n,Map[110][110];

void floyd() {
	for (int k = 1; k <= 100; k++)
		for (int i = 1; i <= 100; i++)
			for (int j = 1; j <= 100; j++)
				if (road[i][k] && road[k][j])	road[i][j] = 1;
}

int spfa() {
	memset(out, 0, sizeof(out));
	memset(vis, 0, sizeof(vis));
	memset(power, 0, sizeof(power));
	queue<int>q;
	power[1] = 100;
	q.push(1);
	vis[1] = 1;
	while (!q.empty()) {
		int f = q.front();
		q.pop();
		out[f]++;
		vis[f] = 0;
		if (out[f] >= n) return road[f][n];//存在正环，判断是否能够到达n点
		for (int i = 1; i <= n; i++) {
			if (Map[f][i] && power[i] < power[f] + energy[i] && power[f] + energy[i]>0) {
				power[i] = power[f] + energy[i];
				if (!vis[i]) {
					q.push(i);
					vis[i] = 1;
				}
			}
		}
	}
	return power[n] > 0;//判断是否大于0
}

int main() {
	while (cin >> n && n > 0) {
		memset(road, 0, sizeof(road));
		memset(Map, 0, sizeof(Map));
		for (int i = 1; i <= n; i++) {
			int k;
			cin >> energy[i] >> k;
			for (int j = 1; j <= k; j++) {
				int node;
				cin >> node;
				road[i][node] = 1;
				Map[i][node] = 1;
			}
		}
		floyd();
		if (!road[1][n])	cout << "hopeless" << endl;//判断是否能够到达
		else {
			if (!spfa())	cout << "hopeless" << endl;
			else  cout << "winnable" << endl;
		}
	}
}