poj1985 java

POJ 1985 是一道经典的图论题目，题目名称为 "Cow Marathon"。这道题目要求在一个无向图中找到一条最长的路径，这条路径满足以下条件：
1. 路径上的所有节点都是树中的节点。
2. 路径上的节点不能重复。

为了解决这道题目，我们可以使用深度优先搜索（DFS）或者广度优先搜索（BFS）来遍历图，并找到最长的路径。以下是使用 Java 实现的代码示例：

import java.util.*;

public class CowMarathon {
    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    static List<List<Edge>> graph = new ArrayList<>();
    static int maxDistance = 0;
    static int maxNode = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int weight = scanner.nextInt();
            graph.get(from).add(new Edge(to, weight));
            graph.get(to).add(new Edge(from, weight));
        }

        boolean[] visited = new boolean[n + 1];
        dfs(1, 0, visited);

        Arrays.fill(visited, false);
        dfs(maxNode, 0, visited);

        System.out.println(maxDistance);
    }

    static void dfs(int node, int distance, boolean[] visited) {
        visited[node] = true;
        if (distance > maxDistance) {
            maxDistance = distance;
            maxNode = node;
        }

        for (Edge edge : graph.get(node)) {
            if (!visited[edge.to]) {
                dfs(edge.to, distance + edge.weight, visited);
            }
        }
    }
}

### 代码说明：
1. **Edge 类**：用于表示图中的边，包含目标节点和边的权重。
2. **graph**：使用邻接表表示图。
3. **maxDistance**：记录最长路径的长度。
4. **maxNode**：记录最长路径的终点节点。
5. **main 方法**：读取输入数据，构建图，并调用深度优先搜索（DFS）方法。
6. **dfs 方法**：深度优先搜索遍历图，更新最长路径的长度和终点节点。