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来实现,要加上判断是否有环