hdu1317 XYZZY Floyd + Bellman

　　这题，我在学搜索的时候做过。不过好像不叫这名字。

　　1、先用Floyd算法判断图的连通性。如果1与n是不连通的，输出hopeless。

　　2、用Bellman_Ford算法判断是否有正圈，如果某点有正圈，并且该点与第n点是连通的。就输出winnable。当然，没有正圈的情况下，可以到达也是可以的。然后就是如何找正圈的问题。Bellman_Ford算法可以判断有没有负圈。Bellman_Ford是解决最短路问题的，核心是松弛法。如果dist[v]<dist[u]+Map[u][v],则dist[v]=dist[u]+Map[u][v]。在循环n-1次以后，如果还存在dist[v]<dist[u]+Map[u][v]，则说明有负圈。这样，我们找正圈也有方法了：dist数组初始化为负无穷。如果dist[v]>dist[u]+Map[u][v],则dist[v]=dist[u]+Map[u][v]。循环n-1次以后，如果还存在dist[v]>dist[u]+Map[u][v]，则说明有正圈。

　　其中，要注意的是。可以往下一房间走的条件是当前的能量值大于0。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = , M = N*N/, INF=0x3f3f3f3f;

int dist[N],f[N][N], g[N];

struct node

{

    int x,y;

}e[M];

int n,m;

void floyd()

{

    int i,j,k;

    for(k=;k<=n;k++)

        for(i=;i<=n;i++)

            for(j=;j<=n;j++)

                f[i][j]=f[i][j]||(f[k][j]&&f[i][k]);

}

bool bellman_ford(int s)

{

    int i,j,k;

    for(i=;i<=n;i++) dist[i]= -INF;

    dist[s]=;

    for(i=;i<n;i++) //n-1次

    {

        for(j=;j<m;j++)

        {

            int x=e[j].x, y=e[j].y;

            if(dist[y]<dist[x] + g[y]&&dist[x]+g[y]>)

                dist[y]=dist[x] + g[y];

        }

    }

    for(j=;j<m;j++)

    {

        int x=e[j].x, y=e[j].y;

        if(dist[y]<dist[x] + g[y]&&dist[x]+g[y]>&&f[y][n]) return ;  //有负环回路

    }

    return dist[n]>;

}

int main()

{

    //freopen("test.txt","r",stdin);

    int i,j,k,t;

    while(scanf("%d",&n)!=EOF)

    {

        if(n==-) break;

        m=;

        memset(f,,sizeof(f));

        for(i=;i<=n;i++)

        {

            scanf("%d%d",&g[i],&j);

            while(j--)

            {

                scanf("%d",&k);

                f[i][k]=;

                e[m].x=i;e[m].y=k;

                m++;

            }

        }

        floyd();

        if(!f[][n])

        {

            printf("hopeless\n");

            continue;

        }

        if(bellman_ford()) printf("winnable\n");

        else printf("hopeless\n");

    }

    return ;

}

　　PS:我感觉写解题报告还是很有必要的。让自己去总结，弄明白解题思路。当然，也可以给别人提供一些思路。

巴特西

hdu1317 XYZZY Floyd + Bellman_Ford

最新文章

热门文章