UVAOJ10557 | 哈喽哈咯

Written by razrlele 23:29 February 14, 2015

这个题最关键的部分就是对于环的处理。

先记录下每个点是否已经访问，并且到达那个点时候的能量值，然后碰见环再次访问已经访问过的点的时候，如果能量大于之前，就说明通过这个环能量可以增长到无限大，然后再开启另一个DFS探测环是否有到达终点的路线，如果有那么直接就是winnable，否则的话直接放弃这个环。

100

101

102

103

104

105

106

107

108

109

110

111

112

/********************************************************

* File Name: uvaoj10557.cpp

* Author: razrLeLe

* Mail: razrlele@gmail.com

* Homepage: https://yueyu.io

* Created Time: Sat 14 Feb 2015 09:23:00 PM CST

******************************************************/

#include "vector"

#include "set"

#include "deque"

#include "queue"

#include "algorithm"

#include "functional"

#include "iostream"

#include "cstdio"

#include "cmath"

#include "cstdlib"

#include "string"

#include "cstring"

#include "string.h"

#include "map"

#include "cctype"

#include "list"

#include "stack"

using namespace std;

#define INF 0x3f3f3f3f

#define LOCAL

const int maxn = 110;

int grid[maxn][maxn];

int energy[maxn];

int route[maxn];

int roomnum;

int vis[maxn];

bool reachable, winnable;

void DFS_TEST(int a)

{

if(a == roomnum)

reachable = true;

if(reachable)

return ;

vis[a] = 1;

for(int i = 1; i <= roomnum; i++)

if(grid[a][i] && vis[i] == -1)

DFS_TEST(i);

return ;

}

void DFS(int num, int e)

{

if(e+energy[num] <= 0 || e+energy[num] <= route[num] || winnable)

return;

e += energy[num];

if(num == roomnum)

{

winnable = true;

return ;

}

if(route[num] == -1)

{

route[num] = e;

}

else if(e > route[num])

{

memset(vis, -1, sizeof(vis));

reachable = false;

DFS_TEST(num);

if(reachable)

winnable = true;

return ;

}

for(int i = 1; i <= roomnum; i++)

if(grid[num][i])

DFS(i, e);

return ;

}

int main()

{

#ifdef LOCAL

freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/out.txt", "w", stdout);

#endif

while(scanf("%d", &roomnum) && roomnum >= 0)

{

memset(grid, 0, sizeof(grid));

memset(route, -1, sizeof(route));

for(int i = 1; i <= roomnum; i++)

{

int doornum, door;

scanf("%d %d", &energy[i], &doornum);

while(doornum--)

{

scanf("%d", &door);

grid[i][door] = 1;

}

winnable = false;

DFS(1, 100);

if(winnable)

printf("winnable\n");

else

printf("hopeless\n");

}

return 0;

}