hdu 1317 XYZZY（bellman + Floyed）

题目：http://acm.split.hdu.edu.cn/showproblem.php?pid=1317

题意：初始值100，每个房间有正值或负值，加上每个值，每个房间可以走好多次，看最后走到n是否为0。保证每次到房间都>0。

分析：有正环即一定可行，用bellman-Ford判断正环，改一改即可，dist改为-inf，u+w<v改为大于。没环dist【n】>0即可。

    用Floyed判断环和n是否联通。

/*
用bellman-Ford不仅是只能找负权环这么简单；
要找：1.有正环，且与1，n连通。2.最短路>0;
*/
#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <cstring>
using namespace std;

const int maxn=105;
const int maxm=maxn*maxn/2;
const int inf= 0x3f3f3f3f;
int n,num,dist[maxn];
int d[maxn][maxn];

void floyed(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=d[i][j]||(d[i][k]&&d[k][j]);
}
struct Edge{
    int u;      //边的起点
    int v;      //边的终点
    int w;
}edge[maxm];

bool Bellman_Ford(int s){
    int i,j;
    for(i=1;i<=n;i++)
        dist[i]=-inf;
    dist[s]=100;
    for(i=1;i<n;i++){
        for(j=0;j<num;j++)
        if(dist[edge[j].u]+edge[j].w>dist[edge[j].v]&&dist[edge[j].u]+edge[j].w>0){  //后半句保证了到一个房间始终>0
            dist[edge[j].v]=dist[edge[j].u]+edge[j].w;                  //否则不会赋到n，dist[n]仍为-inf
        }
    }
    for(i=0;i<num;i++)
        if(dist[edge[i].u]+edge[i].w>dist[edge[i].v]&&dist[edge[i].u]+edge[i].w>0&&d[edge[i].v][n])
        return true;         //经过n-1次的松弛操作后还能更新，说明存在负权环
    return dist[n]>0;        //如果没有正环，>0就OK
}

int main(){
    while(scanf("%d",&n)!=EOF){
        if(n==-1) break;
        int val,k,en;
        num=0;
        memset(d,0,sizeof(d));
        memset(edge,0,sizeof(edge));
        for(int i=1;i<=n;i++){
            scanf("%d%d",&val,&k);
            for(int j=1;j<=k;j++){
                scanf("%d",&en);
                d[i][en]=1;
                edge[num].u=i;
                edge[num].v=en;
                edge[num++].w=val;
            }
        }
        floyed();
        if(!d[1][n]){
            printf("hopeless\n");
            continue;
        }
        if(Bellman_Ford(1)) printf("winnable\n");
        else printf("hopeless\n");
    }
    return 0;
}