当前位置：网站首页>Gamer questions

Gamer questions

2022-07-27 10:37:00 【chengqiuming】

One Link to original question

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

Two Input and output

1 Input

The input contains several test cases . The... Of each test case 1 All lines are n, Indicates the number of rooms . Next is n Information about rooms . Each room information includes ： room i Energy value of 、 Leave the room i The number of doors 、 room i List of rooms that can be reached through the door . After the last test case, it contains -1 The line of .

2 Output

If the player is likely to win , The output winnable, Otherwise output hopeless.

3、 ... and Input and output samples

1 Input

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 Output

hopeless
hopeless
winnable
winnable

Four analysis

According to the input sample 1, The constructed diagram is shown in the following figure , Not to 5 The energy value of room No. 1 is exhausted , Output “hopeless”.

According to the input sample 4, The constructed diagram is shown in the following figure , It has a positive ring and can reach the end , Output “winnable”

5、 ... and Algorithm design

1 use Floyd Algorithm judges connectivity , Judge whether or not from 1 Go to room No n Room number , If not connected, it ends .

2 use SPFA The algorithm judges whether there is a positive ring , stay cnt[v]>=n Sometimes there is a positive ring , Judge whether the point on the ring is connected to the end . If there is no positive ring , Then judge whether the energy value of the longest path to the destination is greater than 0 that will do .

Be careful ： The data given by this problem is the energy value of each node , Not the ability value of the edge , Need to use Floyd Algorithm judges connectivity , So we use adjacency matrix to store graph .

6、 ... and Code

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[]; // Record the strength value of each point 
    static int cnt[];  // Record the number of visits to each point 
    static boolean g[][];
    static boolean vis[];
    static boolean reach[][];

    //  Judge connectivity 
    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) { //  Determine the sum of positive rings and find the maximum energy value 
        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)// Positive ring 
                            return reach[v][n]; // return v To n Is it connected 
                        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();
    }
}