最大传播链

题目描述

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

网络监控规则：

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

流量传播链路：

• 链路条件： 若两个关键节点具有"直接关联"关系，且发生时间戳 $t$ 不同，则流量从时间较早的基站流向时间较晚的基站。
  • 注意：若两个关联的关键节点发生时间完全相同，则它们之间无法建立有效的传播链路。
• 传播链条： 传播链条是由一系列关键节点通过有向链路首尾相连构成的路径。
• 衡量指标： 链条的规模为该路径上所有节点服务的用户数 Users 之和。
• 任务： 计算全网中可能形成的所有传播链条中，能够覆盖的最大用户总数。

输入格式

• 第1行：3个整数 $N$（基站总数，$1 \leq N \leq 200$）、$\varepsilon_{dist}$（空间阈值）和 $W_{threshold}$（负载阈值）。
• 第2行到第 $N+1$ 行，每行包含5个整数：$x, y, t, w, \text{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

说明： 三个基站互为邻居，但每个基站的邻域负载和仅为 $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

说明： 基站 2 和 3 是关键节点（各自负载和为 $200 + 200 = 400 \geq 150$），形成有向边 $2 \to 3$，用户数 $100 + 100 = 200$。

---

解题思路

第一步：理解问题本质

本题是一个多阶段处理的有向图最长路径问题：

1. 筛选关键节点
2. 构建有向图（时间早 → 时间晚）
3. 求最长路径（以用户数为权重）

第二步：暴力解法

枚举所有可能的路径组合，计算每条路径的用户数。由于最多 200 个节点，枚举所有路径是指数级的，不可行。

第三步：最优解法 — 记忆化搜索

由于图是有向的（按时间排序），不存在环，因此这是一个 DAG（有向无环图）。DAG 上的最长路径可以用记忆化搜索（DFS + 缓存）在 $O(N^2)$ 内解决。

具体步骤：

1. 关键节点识别： 对每个节点，计算其邻域（曼哈顿距离 $\leq \varepsilon$）的负载之和
2. 建图： 在关键节点间，若距离满足条件且时间不同，建立有向边（时间小 → 时间大）
3. 记忆化搜索： dfs(u) 表示从节点 $u$ 出发能获得的最大用户数

---

完整代码实现

"""
最大传播链 - DAG 最长路径 + 记忆化搜索

输入格式：
- 第1行：N eps W_threshold
- 接下来 N 行：x y t w Users

输出格式：
- 最大用户数
"""

import sys
from functools import lru_cache

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    eps = int(next(it))
    W_threshold = int(next(it))
    nodes = []
    for _ in range(N):
        x = int(next(it)); y = int(next(it)); t = int(next(it))
        w = int(next(it)); users = int(next(it))
        nodes.append((x, y, t, w, users))

    # 1. 判断关键节点
    is_key = [False] * N
    for i in range(N):
        xi, yi, _, wi, _ = nodes[i]
        total_w = wi
        for j in range(N):
            if i == j:
                continue
            xj, yj, _, wj, _ = nodes[j]
            if abs(xi - xj) + abs(yi - yj) <= eps:
                total_w += wj
        if total_w >= W_threshold:
            is_key[i] = True

    key_indices = [i for i in range(N) if is_key[i]]
    if not key_indices:
        print(0)
        return

    # 2. 构建有向图
    adj = [[] for _ in range(N)]
    for i in key_indices:
        xi, yi, ti, _, _ = nodes[i]
        for j in key_indices:
            if i == j:
                continue
            xj, yj, tj, _, _ = nodes[j]
            if abs(xi - xj) + abs(yi - yj) <= eps and ti != tj:
                if ti < tj:
                    adj[i].append(j)

    # 3. 记忆化搜索
    @lru_cache(maxsize=None)
    def dfs(u):
        best = nodes[u][4]
        for v in adj[u]:
            best = max(best, nodes[u][4] + dfs(v))
        return best

    ans = 0
    for u in key_indices:
        if adj[u]:
            ans = max(ans, dfs(u))
    print(ans)

if __name__ == "__main__":
    solve()

---

示例推演

以样例 2 为例：

输入：

节点	x	y	t	w	Users
0	0	0	10	100	10
1	1	0	20	100	10
2	5	5	10	200	100
3	5	6	30	200	100

关键节点判定：

• 节点 0：邻居 {0, 1}，负载和 = 100 + 100 = 200 $\geq$ 150 ✓
• 节点 1：邻居 {0, 1}，负载和 = 200 $\geq$ 150 ✓
• 节点 2：邻居 {2, 3}，负载和 = 200 + 200 = 400 $\geq$ 150 ✓
• 节点 3：邻居 {2, 3}，负载和 = 400 $\geq$ 150 ✓

建图：

• 节点 0 (t=10) → 节点 1 (t=20)：距离 = 1 $\leq$ 1 ✓
• 节点 2 (t=10) → 节点 3 (t=30)：距离 = 1 $\leq$ 1 ✓
• 节点 1 和节点 3：距离 = $\sqrt{41}$，曼哈顿距离 = 11 > 1，不连边

最长路径：

• 路径 0→1：用户数 = 10 + 10 = 20
• 路径 2→3：用户数 = 100 + 100 = 200
• 最大值 = 200

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力枚举	O(N!)	O(N)	枚举所有路径，不可行
记忆化搜索	O(N²)	O(N)	DAG 最长路径，N ≤ 200

---

易错点总结

1. 关键节点判定包含自身

计算邻域负载和时，不要忘记加上自身的负载 $w_i$。

2. 时间相同不能建边

若两个关键节点时间戳相同，即使距离满足条件，也不能建立传播链路。

3. 边的方向

只能从时间早的节点指向时间晚的节点，是有向图。

4. 孤立节点的处理

没有出边的关键节点不参与答案计算（dfs 返回自身用户数，但不更新 ans）。

---

扩展思考

• 拓扑排序替代 DFS： 也可以用拓扑排序 + DP 求解 DAG 最长路径，避免递归深度问题。
• 多源最长路径： 本题从每个有出边的节点出发搜索，等价于求所有路径的最大值。
• 实际应用： 网络流量溯源、疫情传播链追踪、社交网络影响力分析等。

---

相关题目

• 平衡路径计数 — 二叉树上的路径问题