POJ 1932 XYZZY(Floyd传递闭包+BellmanFord判环)

POJ 1932 XYZZY(Floyd传递闭包+BellmanFord判环)

http://poj.org/problem?id=1932

题意:有N个房间,编号从1到N.现在你初始有100点血,从1号房间出发,你必须走到N号房间才赢.不过每间房间有一个值,如果为正,你加上相应的血量.如果为负,你扣去相应的血量.现在问你是否能到达N房间且中途血量必须大于0.

分析:

本题很多坑.

首先我们无视各个房间的血量数目,用Floyd传递闭包看看从i房间是否能到n房间.如果1号房间都不能到n房间,那么一切都是虚的.

然后我们用BellmanFord算法来求d[i],d[i]表示从1号房间到i号房间时的最大能量数目.这里注意i必须是能从i到n的节点且这里是大值替换小值.

如果BellmanFord算法循环次数超过了n次,那么说明存在正环,那么这个环肯定是从1号点出发能到的,且这个环上的点肯定能到n号房间的.(因为我们在BellmanFord算法松弛的时候,只松弛那些能连上n号房间的点).

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100+10;

int n;
bool map[maxn][maxn],connect[maxn][maxn];
int val[maxn],d[maxn];

int main()
{
    while(scanf("%d",&n)==1&&n!=-1)
    {
        memset(map,0,sizeof(map));
        memset(connect,0,sizeof(connect));
        memset(d,-1,sizeof(d));
        for(int i=1;i<=n;i++)
        {
            int num;
            scanf("%d%d",&val[i],&num);
            while(num--)
            {
                int v;
                scanf("%d",&v);
                map[i][v]=connect[i][v]=true;
            }
        }
        for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(connect[i][k]&&connect[k][j])
            connect[i][j]=true;
        if(connect[1][n]==false)
        {
            printf("hopeless\n");
            continue;
        }
        connect[n][n]=true;

        d[1]=100;
        int k;//Bellman-ford求最长路径
        for(k=0;k<n;k++)
        {
            bool flag=true;
            for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            if(map[i][j] && connect[j][n] && d[i]>0 && d[j] <d[i]+val[j])
            {//必须是连通的,且该店与n也是连通的。 并且前一个点的dist非负
             //j点必须与n连通是因为,如果j与n不连通,但是j存在正环,那就跟n没关系了
                d[j]=d[i]+val[j];
                flag=false;
            }
            if(flag) break;
        }
        if(k>=n || d[n]>=0)
            printf("winnable\n");
        else
            printf("hopeless\n");

    }
    return 0;
}