XYZZY
题目链接：http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=2051
题目大意：
有一副有向图，每个顶点都有一个值。（顶点最多100）现在你从起点出发，能量初值为100，每到一个点，能量值要加上该点的值。如果相加之后能量值小于等于0，就算失败。问能否从起点成功的到达终点。（图中会出现环）
解题思路：
（DFS + BFS）
这道题主要难点是有环，如果出现环，并且每走一次环，能量值增大，那么如果终点和该环相连接，一定可以成功到达。因为可以多走几次环，使得能量值足够到达终点再离开环
所以首先是要判断是否有环：
可以用DFS来实现，用一个energy数组来记录从起点到各个点的能量值，一开始均设置为0。然后通过有向边将能够到达的点的energy值重新赋值，接着对该点进行DFS，如果碰到一个点，energy值已经非0，说明已经成环。
如果此时的energy值大于之前该点的energy值，说明走一遍该循环能量值增大，此时对该点进行BFS，看能否到达终点。
判断能否达到终点：
用BFS来实现，这个就是最为基础的图的搜索，实现从一个点出发，能否到达另一个点。
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 110
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
vector<int> v[maxn];
int value[maxn];
int energy[maxn];
int n;
bool flag = false;
int que[100000];
void bfs(int x)
{
int visit[maxn] = {0};
int i, j, q, font = 0, rear = 1;
que[font] = x;
visit[x] = 1;
while(font < rear)
{
q = que[font++];
if (q == n)
{
flag = true;
return ;
}
for (i = 0; i < v[q].size(); i++)
{
j = v[q][i];
if (!visit[j]) que[rear++] = j, visit[j] = 1;
}
}
}
void dfs(int s)
{
if (flag) return ;
if (s == n && energy[s] > 0)
{
flag = true;
return ;
}
int tol = v[s].size();
for (int i = 0; i < tol; i++)
{
int j = v[s][i];
if (energy[j] && energy[s] + value[j] > energy[j])
{
bfs(j);
if (flag) return ;
}
if (!energy[j] && energy[s] + value[j] > 0)
{
energy[j] = energy[s] + value[j];
dfs(j);
}
}
}
int main ()
{
int i, j, k;
while(scanf("%d", &n) != EOF)
{
if (n == -1) break;
flag = false;
for (i = 1; i <= n; i++)
{
v[i].clear();
scanf("%d%d", value + i, &k);
while(k--)
{
scanf("%d", &j);
v[i].push_back(j);
}
}
energy[1] = 100;
dfs(1);
if (flag) puts("winnable");
else puts("hopeless");
mem(energy, 0);
}
return 0;
}
当然这道题也可以用的SPFA来实现，要加上判断是否有环