题解 | 小红的异常流量传播链

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    // 当前搜索路径上收集的用户总数
    private static long path = 0;
    // 全局最大的用户总数
    private static long result = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int n = Integer.parseInt(s[0]);          // 节点个数
        int dist = Integer.parseInt(s[1]);       // 距离阈值
        int wthreshold = Integer.parseInt(s[2]); // 权重阈值

        Node[] nodes = new Node[n];
        // 读取每个节点的信息
        for (int i = 0; i < n; i++) {
            String[] line = sc.nextLine().split(" ");
            nodes[i] = new Node();
            nodes[i].x = Integer.parseInt(line[0]);
            nodes[i].y = Integer.parseInt(line[1]);
            nodes[i].timeStamp = Integer.parseInt(line[2]);
            nodes[i].weight = Integer.parseInt(line[3]);
            nodes[i].users = Integer.parseInt(line[4]);
        }

        // 按时间戳升序排序，保证后续遍历时时间单调递增
        Arrays.sort(nodes, (a, b) -> a.timeStamp - b.timeStamp);

        // 邻接矩阵：map[i][j] = 1 表示节点i与节点j在曼哈顿距离内
        int[][] map = new int[n][n];

        // 构建图并标记有效节点（权重和达到阈值）
        for (int i = 0; i < n; i++) {
            int temp = nodes[i].weight;   // 当前节点自己的权重计入
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    // 曼哈顿距离
                    int d = Math.abs(nodes[j].x - nodes[i].x) + Math.abs(nodes[j].y - nodes[i].y);
                    if (d <= dist) {
                        map[i][j] = 1;
                        temp += nodes[j].weight;
                        if (temp >= wthreshold) {
                            nodes[i].valid = true;   // 权重和达到阈值，节点有效
                        }
                    }
                }
            }
        }

        // 从每个有效节点出发，深度优先搜索寻找最大路径用户和
        for (int i = 0; i < n; i++) {
            if (nodes[i].valid) {
                path = nodes[i].users;          // 起点用户数计入
                dfs(map, nodes, i);             // 递归搜索
            }
        }
        System.out.println(result);              // 输出最大用户数
    }

    // 节点定义：包含坐标、时间戳、权重、用户数、是否有效
    private static class Node {
        int x;
        int y;
        int timeStamp;
        int weight;
        int users;
        boolean valid;

        Node() {}

        Node(int x, int y, int timeStamp, int weight, int users) {
            this.x = x;
            this.y = y;
            this.timeStamp = timeStamp;
            this.weight = weight;
            this.users = users;
            this.valid = false;
        }
    }

    // 深度优先搜索：沿时间戳递增且有效的邻接节点行走
    private static void dfs(int[][] map, Node[] nodes, int index) {
        for (int i = 0; i < map.length; i++) {
            // 可达、时间更大、并且是有效节点
            if (map[index][i] == 1 && nodes[index].timeStamp < nodes[i].timeStamp && nodes[i].valid) {
                path += nodes[i].users;               // 加入当前节点用户数
                result = Math.max(path, result);      // 更新全局最大值
                dfs(map, nodes, i);                   // 继续向下搜索
                path -= nodes[i].users;               // 回溯，撤销该节点用户数
            }
        }
    }
}