欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

XYZZY HDU1317

程序员文章站 2024-02-24 22:34:10
...

题意:一个游戏,从1号房间走到N号房间,每个房间都会有个能量值(可能为正,可能为负),每进入一个房间,房间的能量值就会加到玩家身上。

思路:求这个图的最长路,如果存在正环且正环能够到达终点则赢,或者到达终点时能量值大于0且整个过程中能量值大于0则赢。判断能不能到达用 Floyd 算法,求最长路用 BellmanFord 算法或 SPFA 算法。

下面是用 BellmanFord 和 Floyd 算法实现的。
自己实现过程中遇到的问题有:忘了每次初始化 G 数组为 0 。。。还有就是BellmanFord 用的不熟,,细节地方出了差错。
代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<utility>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 1000000;
const int MAXN = 110;

struct Edge{
    int from, to;
    Edge(){}
    Edge(int a, int b):from(a),to(b){}
};

int n;
int G[MAXN][MAXN];
int value[MAXN];
int d[MAXN];
vector<Edge> edges;

void Floyd()
{
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                G[i][j] |= G[i][k]&G[k][j];  //Floyd算法判断能否到达
            }
        }
    }
}

bool BellmanFord(int s)
{
    for(int i=1; i<=n; i++) d[i] = -INF;
    d[1] = 100;

    for(int i=1; i<n; i++){
        for(int j=0; j<edges.size(); j++){
            int from = edges[j].from;
            int to = edges[j].to;
            if(d[to] < d[from]+value[to] && d[from]+value[to]>0){   //只有新的值大于 0 才能松弛
                d[to] = d[from]+value[to];
            }
        }
    }

    for(int i=0; i<edges.size(); i++){
        int from = edges[i].from;
        int to = edges[i].to;
        if(d[to] < d[from]+value[to] && d[from]+value[to]>0 && G[to][n]){   //如果存在环,且这个环能够到达终点那么 winnable
            return true;
        }
    }

    return d[n] > 0;
}

void Init()
{
    memset(G, 0, sizeof(G));
    edges.clear();
}

int main()
{
    //freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) == 1 && n!=-1){
        Init();
        for(int i=1; i<=n; i++){
            scanf("%d", &value[i]);
            int m;
            scanf("%d", &m);
            while(m--){
                int x;
                scanf("%d", &x);
                G[i][x] = 1;
                edges.push_back(Edge(i, x));
            }
        }

        Floyd();

        if(G[1][n]){
            if(BellmanFord(1)){
                printf("winnable\n");
            }
            else{
                printf("hopeless\n");
            }
        }
        else{
            printf("hopeless\n");
        }
    }
    return 0;
}

下面是用 Flyod 和 SPFA 算法写的

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<utility>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 1000000;
const int MAXN = 110;

struct Edge{
    int from, to;
    Edge(){}
    Edge(int a, int b):from(a),to(b){}
};

int n;
int G[MAXN][MAXN];
int value[MAXN];
int d[MAXN];
int time[MAXN];
bool inq[MAXN];
vector<Edge> edges;
vector<int> M[MAXN];

void Floyd()
{
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                G[i][j] |= G[i][k]&G[k][j];  //Floyd算法判断连通性
            }
        }
    }
}

bool SPFA(int s)
{
    for(int i=1; i<=n; i++) d[i] = -INF;
    d[s] = 100;
    memset(inq, false, sizeof(inq));
    memset(time, 0, sizeof(time));

    queue<int> que;
    que.push(s);
    inq[s] = true;

    while(!que.empty()){
        int tmp = que.front();  que.pop();

        inq[tmp] = false;

        for(int i=0; i<M[tmp].size(); i++){
            Edge &e = edges[M[tmp][i]];
            if(d[e.to] < d[e.from]+value[e.to] && d[e.from]+value[e.to]>0 ){
                d[e.to] = d[e.from]+value[e.to];
                if(!inq[e.to]){
                    inq[e.to] = true;
                    if(++time[e.to] > n+1) {return G[e.to][n];}
                    que.push(e.to);
                }
            }
        }
    }

    return d[n] > 0;
}

void Init()
{
    memset(G, 0, sizeof(G));
    for(int i=0; i<MAXN; i++){
        M[i].clear();
    }
    edges.clear();
}

int main()
{
    //freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) == 1 && n!=-1){
        Init();

        for(int i=1; i<=n; i++){
            scanf("%d", &value[i]);
            int m;
            scanf("%d", &m);
            while(m--){
                int x;
                scanf("%d", &x);
                G[i][x] = 1;
                edges.push_back(Edge(i, x));
                M[i].push_back(edges.size()-1);
            }
        }

        Floyd();

        if(G[1][n]){
            if(SPFA(1)){
                printf("winnable\n");
            }
            else{
                printf("hopeless\n");
            }
        }
        else{
            printf("hopeless\n");
        }
    }
    return 0;
}