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求最长路的方法，复习了传递闭包。
/* ***********************************************
Author :111qqz
Created Time :2016年05月24日 星期二 20时03分37秒
File Name :code/poj/1932.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=105;
1vector< int > edge[N];
2int a[N];
3bool conc[N][N];
4int in[N]; //统计入队次数，大于n次表明有环。
5bool inq[N];
6int n;
7int d[N];
8void floyd() //传递闭包
9{
10 for ( int k = 1 ; k <= n ; k++)
11 for ( int i = 1 ; i <= n ; i++)
12 for ( int j = 1 ; j <= n ; j++)
13 if (conc[i][k]&&conc[k][j]) conc[i][j] = true;
14}
15bool spfa(int s) //spfa求最长路。
16{
17 ms(in,0);
18 ms(d,0);//因为小于等于0就死，所以初始是0，这样更新的时候一定是正值才更新。
19 ms(inq,false);
20 queue<int>q;
21 q.push(s);
22 inq[s] = true;
23 d[s] = 100;
24 in[s]++;
1 while (!q.empty())
2 {
3 int u = q.front();
4 q.pop();
5 inq[u]=false;
1 int siz = edge[u].size();
2 if (in[u]>n) break; //有环
3 for ( int i = 0 ; i < siz ; i++)
4 {
5 int v = edge[u][i];
6 // cout<<"v:"<<v<<" d[u]:"<<d[u]<<" a[v]:"<<a[v]<<endl;
7 if (d[v]<d[u]+a[v])
8 {
9 d[v] = d[u] + a[v];
10 if (inq[v]) continue;
11 inq[v] = true;
12 q.push(v);
13 in[v]++;
14 }
15 }
16 }
17 // cout<<"d[n]:"<<d[n]<<endl;
18 if (d[n]>0) return true; //不会存在中间有非正最后为正的情况，因为初始值为0，中间为0或者负不会更新。
19 // d[n]也只有0和大于0两种可能。
floyd();
for ( int i = 1 ; i <= n ; i++) //如果有正环并且环上的某点可以联通1和n那么也有解。只要跑足够次就可以把eng变得足够大
if (in[i]>n&&conc[1][i]&&conc[i][n]) return true;
1 return false;
2}
3int main()
4{
5 #ifndef ONLINE_JUDGE
6 freopen("code/in.txt","r",stdin);
7 #endif
1 while (scanf("%d",&n)!=EOF)
2 {
3 ms(conc,false);
4 if (n==-1) break;
5 for ( int i = 0 ; i <= n ; i++) edge[i].clear();
6 ms(conc,false);
7 for ( int i = 1 ; i <= n ; i++)
8 {
9 scanf("%d",&a[i]);
10 int num;
11 scanf("%d",&num);
12 while (num--)
13 {
14 int x;
15 scanf("%d",&x);
16 edge[i].push_back(x);
17 conc[i][x] = true;
18 }
19 }
1 if (spfa(1))
2 puts("winnable");
3 else puts("hopeless");
4 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}