题目分析

这道题分为三个步骤：

1. 关键节点识别：根据空间距离和负载阈值筛选出关键基站
2. 有向图构建：在关键节点之间根据时间和空间关系建立有向边
3. 最长路径求解：在DAG上找点权和最大的路径

解题思路详解

题目背景

在网络监控中，异常流量的流动通常具有局部聚集性。监控系统需要识别出高负载的基站（关键节点），并判断流量在这些节点之间定向的传播链的最长路径。

题目描述

网络监控规则

• 直接关联：对于基站 $A$ 和 $B$，若其曼哈顿距离 $|x_A - x_B| + |y_A - y_B| \leq \varepsilon_{dist}$，则判定两者具有直接关联。
• 关键节点判定：计算一个基站及其所有具有“直接关联”属性的基站（含自身）的流量负载 $w$ 之和。若该总和 $\ge W_{threshold}$，则该基站被判定为关键节点。

• 流量传播链路

• 流量只能在关键节点之间定向流动，规则如下：

• 链路条件：若两个关键节点具有“直接关联”关系，且发生时间戳 $t$ 不同，则流量从时间较早的基站流向时间较晚的基站。

• 注意：若两个关联的关键节点发生时间完全相同，则它们之间无法建立有效的传播链路。

• 传播链条 传播链条是由一系列关键节点通过有向链路首尾相连构成的路径。

• 衡量指标：链条的规模为该路径上所有节点服务的用户数 $Users$ 之和。
• 任务：计算全网中可能形成的所有传播链条中，能够覆盖的最大用户总数。

处理流程指引

• 节点识别：基于空间距离和流量负载阈值，从所有基站中筛选出满足要求的关键节点。

• 构建拓扑：在关键节点间，基于空间关联和时间先后顺序（时间早 → 时间晚）建立定向传播关系。

• 路径计算：在构成的有向传播网络中，寻找一条或多条连续路径，使得累计服务的用户数 $Users$ 达到最大。

输入描述

第 $1$ 行：包含 $3$ 个整数 $N$（基站总数，$1 \le N \le 200$）、$\varepsilon_{dist}$（空间阈值）和 $W_{threshold}$（负载阈值）。

第 $2$ 行到 $N+1$ 行，每行包含 $5$ 个整数：$x, y, t, w, Users$。

所有坐标、时间戳、负载和用户数的取值范围均为 $[0, 10^9]$。

输出描述

输出一个整数，代表最大用户数。若全网无法形成任何链路或关键节点，输出 $0$。

样例1

输入

3 1 500
0 0 10 100 50
1 0 20 100 50
0 1 30 100 50

输出

0

说明

节点识别：三个基站虽然互为邻居，但每个基站能查到的邻域最大负载和仅为 $100 \times 3 = 300$。判定门槛 $W_{threshold} = 500$，因 $300 < 500$，图中没有任何基站能成为关键节点。

结论：由于传播链路只能在关键节点间建立，无关键节点即无法形成链条，输出 $0$。

样例2

输入

4 1 150
0 0 10 100 10
1 0 20 100 10
5 5 10 200 100
5 6 30 200 100

输出

200

说明

节点识别：基站 $0$ & $1$：曼哈顿距离为 $1$，互为邻居。各自负载均为 $100 + 100 = 200 > 150$，均为关键节点。