POJ3259Bellman-Ford算法实现

在本题中，我们探讨了一个关于农夫约翰探索农场的问题。农夫约翰发现了一些虫洞，这些虫洞可以让他回到过去的时间点。为了帮助约翰确定是否可以通过某些路径和虫洞返回出发点之前的时间，我们需要使用Bellman-Ford算法来检测是否存在负权环。

Bellman-Ford算法是一种用于计算单源最短路径的算法，特别适用于处理带有负权重边的图。在这个问题中，虫洞被视为具有负权重的边。具体步骤如下：

• 定义图的邻接表表示法。
• 初始化距离数组、前驱数组、计数数组以及队列。
• 通过广度优先搜索（BFS）遍历图，更新每个节点的距离值。
• 检查是否存在负权环，即某个节点被加入队列的次数超过节点总数。

以下是完整的Java代码实现：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class POJ3259 {
    private static List[] graph;
    private static int[] distances;
    private static int[] predecessors;
    private static int[] visitCounts;
    private static boolean[] inQueue;
    private static Queue queue;
    private static int numNodes;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numFarms = scanner.nextInt();
        for (int i = 0; i             numNodes = scanner.nextInt();
            int numPaths = scanner.nextInt();
            int numWormholes = scanner.nextInt();
            initializeGraph(numNodes);
            readInput(scanner, numPaths, numWormholes);
            System.out.println(checkNegativeCycle() ? "NO" : "YES");
        }
    }

    private static void initializeGraph(int n) {
        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    private static void readInput(Scanner scanner, int paths, int wormholes) {
        for (int i = 0; i             int start = scanner.nextInt(), end = scanner.nextInt(), time = scanner.nextInt();
            graph[start].add(new Node(start, end, time));
            graph[end].add(new Node(end, start, time));
        }
        for (int i = 0; i             int start = scanner.nextInt(), end = scanner.nextInt(), time = -scanner.nextInt();
            graph[start].add(new Node(start, end, time));
        }
    }

    private static boolean checkNegativeCycle() {
        distances = new int[numNodes + 1];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[1] = 0;
        predecessors = new int[numNodes + 1];
        visitCounts = new int[numNodes + 1];
        inQueue = new boolean[numNodes + 1];
        queue = new LinkedList<>();
        queue.offer(1);
        inQueue[1] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            inQueue[current] = false;
            for (Node node : graph[current]) {
                if (distances[current]  distances[current] + node.dist) {
                    distances[node.to] = distances[current] + node.dist;
                    predecessors[node.to] = current;
                    if (!inQueue[node.to]) {
                        queue.offer(node.to);
                        inQueue[node.to] = true;
                        if (++visitCounts[node.to] > numNodes) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}

class Node {
    int from;
    int to;
    int dist;

    public Node(int from, int to, int dist) {
        this.from = from;
        this.to = to;
        this.dist = dist;
    }
}

通过上述代码，我们可以有效地利用Bellman-Ford算法来检测负权环，从而判断是否可以通过路径和虫洞返回出发点之前的时间。希望这段代码能够帮助你更好地理解和应用Bellman-Ford算法。