游戏玩家问题

一 原问题链接

XYZZY - HDU 1317 - Virtual Judgehttps://vjudge.net/problem/HDU-1317

二 输入和输出

1 输入

输入包含几个测试用例。每个测试用例的第1行都为n，表示房间数。接下来是 n 个房间的信息。每个房间信息都包括：房间 i 的能量值、离开房间 i 的门的数量、房间 i 可以通过门到达的房间列表。在最后一个测试用例之后是包含 -1 的行。

2 输出

如果玩家有可能获胜，则输出 winnable，否则输出 hopeless。

三 输入与输出样例

1 输入

5

0 1 2

-60 1 3

-60 1 4

20 1 5

0 0

5

0 1 2

20 1 3

-60 1 4

-60 1 5

0 0

5

0 1 2

21 1 3

-60 1 4

-60 1 5

0 0

5

0 1 2

20 2 1 3

-60 1 4

-60 1 5

0 0

-1

2 输出

hopeless

hopeless

winnable

winnable

四 分析

根据输入样例1，构建的图如下图所示，到不了 5 号房间能量值就耗尽了，输出“hopeless”。

根据输入样例 4，构建的图如下图所示，有正环且可以到达终点，输出“winnable”

五 算法设计

1 用 Floyd 算法判断连通性，判断能否从 1 号房间走到 n 号房间，如果不连通则结束。

2 用 SPFA 算法判断有没有正环，在 cnt[v]>=n 时有正环，判断环上一点到终点是否连通。如果没有正环，则判断到达终点的最长路径的能量值是否大于 0 即可。

注意：该问题给出的数据是每个节点的能量值，而不是边的能力值，需要用 Floyd 算法判断连通性，因此用邻接矩阵来存储图。

六 代码

package graph.hdu1317;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Hdu1317 {
    static final int maxn = 105;
    static int n;
    static int energy[];
    static int power[]; //记录到每一点的力量值
    static int cnt[];  //记录访问每一个点的次数
    static boolean g[][];
    static boolean vis[];
    static boolean reach[][];

    // 判断连通性
    static void floyd() {
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (reach[i][j] || (reach[i][k] && reach[k][j]))
                        reach[i][j] = true;
    }

    static boolean spfa(int s) { // 判正环和求最大能量值
        Queue<Integer> q = new LinkedList<>();
        power = new int[maxn];
        vis = new boolean[maxn];
        cnt = new int[maxn];
        power[s] = 100;
        q.add(s);
        vis[s] = true;
        cnt[s]++;
        while (!q.isEmpty()) {
            int v = q.peek();
            q.poll();
            vis[v] = false;
            for (int i = 1; i <= n; i++) {
                if (g[v][i] && power[i] < power[v] + energy[i] && power[v] + energy[i] > 0) {
                    power[i] = power[v] + energy[i];
                    if (!vis[i]) {
                        if (++cnt[i] >= n)//有正环
                            return reach[v][n]; //返回v到n是否连通
                        vis[i] = true;
                        q.add(i);
                    }
                }
            }
        }
        return power[n] > 0;
    }

    static void solve() {
        int k, door;
        while (true) {
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            if (n == -1) {
                return;
            }
            g = new boolean[maxn][maxn];
            reach = new boolean[maxn][maxn];
            energy = new int[maxn];


            for (int i = 1; i <= n; i++) {
                energy[i] = scanner.nextInt();
                k = scanner.nextInt();

                for (int j = 1; j <= k; j++) {
                    door = scanner.nextInt();
                    g[i][door] = true;
                    reach[i][door] = true;
                }
            }
            floyd();
            if (!reach[1][n]) {
                System.out.println("hopeless");
                continue;
            }
            if (spfa(1) == true)
                System.out.println("winnable");
            else
                System.out.println("hopeless");
        }
    }

    public static void main(String[] args) {
        solve();
    }
}

七 测试

绿色为输入，白色为输出。