poj 1932 XYZZY (floyd传递闭包+spfa求最长路)
题意：初始在点1，有100点能量，然后每个点有一个能量值【-100,100】，经过某个点会加上这个点的能量值，问能否找到一条到点n且的路线，且路径任何点的能量值一直为正。一共不超过100个点。
思路：像样例中是直接联通，一路上的能量值都大于0，这是有解的一种情况。另一种是存在一个正环，可能一次路过后面的能量值不够，但是我们可以走多次啊。
因为要求每一步的能量值都大于0，那么我们可以初始化d[]数组为0，然后用spfa求最长路（只需要把那个三角形等式换个方向即可）
如果可以直接联通，也就是d[n]>0，那么有解。
还有可能是存在一个环（判断环的方法是用一个数组在spfa的时候统计每个点入队的次数，如果一个点的入队次数大于n，那么就存在环，且这个点在环中）
但是我们还要保证起点1和终点n是经过这个环的。
所以先跑一发floyd. 其实n才100也算给了提示吧，不用floyd的话没道理这么小的数据。。？
感觉这道题很棒，把spfa和floyd结合在了一起。
学到了判断环的方法，spfa求最长路的方法，复习了传递闭包。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月24日 星期二 20时03分37秒
4File Name :code/poj/1932.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=105;
34
35vector< int > edge[N];
36int a[N];
37bool conc[N][N];
38int in[N]; //统计入队次数，大于n次表明有环。
39bool inq[N];
40int n;
41int d[N];
42void floyd() //传递闭包
43{
44 for ( int k = 1 ; k <= n ; k++)
45 for ( int i = 1 ; i <= n ; i++)
46 for ( int j = 1 ; j <= n ; j++)
47 if (conc[i][k]&&conc[k][j]) conc[i][j] = true;
48}
49bool spfa(int s) //spfa求最长路。
50{
51 ms(in,0);
52 ms(d,0);//因为小于等于0就死，所以初始是0，这样更新的时候一定是正值才更新。
53 ms(inq,false);
54 queue<int>q;
55 q.push(s);
56 inq[s] = true;
57 d[s] = 100;
58 in[s]++;
59
60 while (!q.empty())
61 {
62 int u = q.front();
63 q.pop();
64 inq[u]=false;
65
66 int siz = edge[u].size();
67 if (in[u]>n) break; //有环
68 for ( int i = 0 ; i < siz ; i++)
69 {
70 int v = edge[u][i];
71 // cout<<"v:"<<v<<" d[u]:"<<d[u]<<" a[v]:"<<a[v]<<endl;
72 if (d[v]<d[u]+a[v])
73 {
74 d[v] = d[u] + a[v];
75 if (inq[v]) continue;
76 inq[v] = true;
77 q.push(v);
78 in[v]++;
79 }
80 }
81 }
82 // cout<<"d[n]:"<<d[n]<<endl;
83 if (d[n]>0) return true; //不会存在中间有非正最后为正的情况，因为初始值为0，中间为0或者负不会更新。
84 // d[n]也只有0和大于0两种可能。
85
86 floyd();
87
88 for ( int i = 1 ; i <= n ; i++) //如果有正环并且环上的某点可以联通1和n那么也有解。只要跑足够次就可以把eng变得足够大
89 if (in[i]>n&&conc[1][i]&&conc[i][n]) return true;
90
91 return false;
92}
93int main()
94{
95 #ifndef ONLINE_JUDGE
96 freopen("code/in.txt","r",stdin);
97 #endif
98
99 while (scanf("%d",&n)!=EOF)
100 {
101 ms(conc,false);
102 if (n==-1) break;
103 for ( int i = 0 ; i <= n ; i++) edge[i].clear();
104 ms(conc,false);
105 for ( int i = 1 ; i <= n ; i++)
106 {
107 scanf("%d",&a[i]);
108 int num;
109 scanf("%d",&num);
110 while (num--)
111 {
112 int x;
113 scanf("%d",&x);
114 edge[i].push_back(x);
115 conc[i][x] = true;
116 }
117 }
118
119 if (spfa(1))
120 puts("winnable");
121 else puts("hopeless");
122 }
123
124 #ifndef ONLINE_JUDGE
125 fclose(stdin);
126 #endif
127 return 0;
128}