2014-07-07 19:21:17
题意：给出有向图，每个节点（1到n）都有自己的值，可正可负。初始有100点能量值，每走到一个节点当前能量值就加上节点的值。如果能从1走到n（每个节点可以重复走），且过程中能量值恒 > 0，则win，否则fail。
思路：根据题目给出的数据构建一个邻接矩阵（用以保存连通关系），再开v【k】数组记录每个节点的值，e【k】记录前一次到达k节点的能量值。然后双重DFS，DFS1用来判断连通性，即能否从1走到n（不考虑能量值），DFS2用来判断在1到n构成的有向图中能否构成增量环（自己搞的名字，表示走完一圈后能量值增加的环），每搜到一个增量环就从这个环开始DFS1，判断能否从这个环开始走到终点（此处很重要，仔细思索！）10A，我承认我写搓了QAQ,TAT！
1 #include <cstdio> 2 #include <queue> 3 #include <cmath> 4 #include <cstring> 5 #include <algorithm> 6 #include <iostream> 7 using namespace std; 8 9 int flag1,flag2,n,g[105][105],v[105],e[105],used[105]; 10 void Dfs1(int id){ 11 if(flag1) 12 return; 13 used[id] = 1; 14 for(int i = 1; i <= n; ++i){ 15 if(!used[i] && g[id][i]){ 16 if(i == n){ 17 flag1 = 1; 18 return; 19 } 20 Dfs1(i); 21 } 22 } 23 return; 24 } 25 void Dfs2(int id){ 26 if(flag2) 27 return; 28 used[id] = 1; 29 for(int i = 1; i <= n; ++i){ 30 if(g[id][i] && e[id] + v[i] > 0){ 31 if(i == n){ 32 flag2 = 1; 33 return; 34 } 35 if(!used[i]){ 36 e[i] = e[id] + v[i]; 37 Dfs2(i); 38 } 39 if(used[i] && e[id] + v[i] > e[i]){ //增环 40 memset(used,0,sizeof(used)); 41 flag1 = 0; 42 Dfs1(i); 43 if(flag1){ 44 flag2 = 1; 45 return; 46 } 47 } 48 } 49 } 50 } 51 int main(){ 52 int val,num,tmp; 53 while(scanf("%d",&n) == 1){ 54 if(n == -1) break; 55 //init 56 memset(g,0,sizeof(g)); 57 for(int i = 1; i <= n; ++i){ 58 scanf("%d %d",&v[i],&num); 59 while(num--){ 60 scanf("%d",&tmp); 61 g[i][tmp] = 1; 62 } 63 } 64 if(n == 1){ 65 printf("winnable\n"); 66 continue; 67 } 68 flag1 = flag2 = 0; 69 memset(used,0,sizeof(used)); 70 Dfs1(1); 71 int flag11 = flag1; 72 if(flag11){ 73 memset(used,0,sizeof(used)); 74 memset(e,0,sizeof(e)); 75 e[1] = 100; 76 Dfs2(1); 77 } 78 //printf("flag1:%d flag2:%d\n",flag1,flag2); 79 if(flag11 && flag2) printf("winnable\n"); 80 else printf("hopeless\n"); 81 } 82 return 0; 83 }