🎮DAG 阈值猎杀：二分特工的探针三连击！
你是一名网络特工，代号“二分”——不是因为你长得二分，而是你解决问题时总喜欢把答案劈成两半，逼它自己招供。今天你接到的任务比以往更离谱：从总部 0 号节点出发，穿越一张由单向光缆编织的有向无环图（DAG），抵达最后一处未被黑客攻破的数据中心 n-1。沿途的中转服务器，有些还在线（online[i]=true），有些已经挂了。节点之间由单向光缆连接，每条光缆上都贴着一张维修价签 cost，明码标价。
上司甩给你一笔可怜的预算 k，要你挑一条路，把沿途经过的光缆通通维护一遍。规矩很明确：总花费不许超支，沿途服务器必须在线——你总不能对着一台冒烟的机柜敲 ping 吧。
你决定，要在所有合法路径中，找出那个最小边成本最大的路径。为什么盯着最小边？因为短板决定体验，瓶颈决定命运——哪怕路上有一根 1 块钱的劣质网线，它就能把整条万兆光纤拖成PPT播放器。让这条路上最烂的那段，也比其他所有合法路径的最烂段要强——这是属于特工的尊严，也是属于打工人的倔强。
当然，如果连一条合法路径都不存在……那就带着 -1 回去挨批。
二分阈值猎杀
这个问题说白了是个“双约束”修罗场——既要让路径上的最小边成本尽可能大，又要让总成本不超过 k。就像老板既要马儿跑得快，又要马儿不吃草一样。
但你丝毫不慌——"最大化最小值"，这五个字就是二分查找的接头暗号。
如果阈值 x 可行（即存在一条路径，所有边成本 ≥ x，且总成本 ≤ k），那么任何比 x 小的阈值也一定可行（因为放宽了边限制，路径只会更多）。反过来，如果 x 不可行，那么比 x 大的阈值更不可能可行。
单调性成立，猎杀开始。你像切西瓜一样，把答案范围 [l, r] 一分为二，反复猜、反复验证，直到精确命中那个最优阈值。
你给这套"猜答案 → 验答案"的流程起了个中二代号：阈值探针。
def findMaxPathScore(n: int, edges: List[List[int]], online: List[bool], k: int) -> int:
n = len(online)
g = [[] for _ in range(n)]
l, r = float('inf'), 0
# 建图(只走在线节点)和确定边界
for u, v, cost in edges:
if not online[u] or not online[v]:
continue
g[u].append((v, cost))
r = max(r, cost)
l = min(l, cost)
# 阈值探针!
def check(limit: int) -> bool:
# todo: 检查阈值 limit 是否可行
pass
# 二分答案
if not check(l):
return -1
while l <= r:
mid = (l + r) >> 1
if check(mid):
l = mid + 1
else:
r = mid - 1
return r
现在，你必须给这个空壳探针注入灵魂。
check(limit) 要干的事很明确：在只允许走成本 ≥ limit 的边这个前提下，判断能否从 0 走到 n-1，且总花费 ≤ k。
Dijkstra 最短路 + 二分（最稳健的探针）
你脑子里第一个蹦出来的，是图论祖师爷 Dijkstra 老爷子。他老人家的算法精髓就四个字：贪心 + 单调——用一个最小堆永远优先处理当前花费最小的节点，保证第一次抵达就是最优。
现在你把 Dijkstra 改装成一台"阈值检查器"：
- 维护一个
dist数组，记录从起点到每个节点的最小花费，初始时只有dist[0] = 0，其余为正无穷。 - 堆里存
(累计花费, 节点)，每次弹出花费最小的节点。如果当前花费已经超过k——继续走就是贴钱打工，直接return False。 - 如果弹出的恰好是终点
n-1，恭喜，Dijkstra 保证第一次弹出终点就是全局最小总花费，它不超预算，意味着limit肯定可行，return True。 - 如果当前弹出的花费比
dist[u]还大？说明这是个过时记录——之前已经有更便宜的路到过u了，果断扔掉。 - 遍历
u的所有出边，cost < limit的直接无视（太次，配不上你的追求），只对cost >= limit的“硬货”做松弛：如果dist[u] + cost < dist[v]，更新dist[v]并入堆。
这个检查器有多稳？一次 Dijkstra 是 O(m log n)，套上二分 O(log C)，总复杂度 O(m log n log C)，对于题目规模来说，就像用 4090 跑扫雷，绝对稳如老狗。
# 解法一：Dijkstra 最短路
def check(limit: int) -> bool:
dis = [float('inf')] * n
dis[0] = 0
pq = [(0, 0)] # (累计花费, 节点)
while pq:
cur, u = heapq.heappop(pq)
if cur > k:
return False # 超预算，直接死刑
if u == n-1:
return True # 第一次抵达终点 = 最小花费，预算内通关
if cur > dis[u]:
continue # 过时的记录，跳过
for v, cost in g[u]:
if cost < limit:
continue
if dis[v] > dis[u] + cost:
dis[v] = dis[u] + cost
heapq.heappush(pq, (dis[v], v))
return False
你刚觉得Dijkstra这把重剑稳如老狗，但转念一想——这图可是DAG啊！有向无环，意味着路径天生有序，根本不需要堆去维护什么优先级。于是你决定换一把更轻巧的匕首。
记忆化搜索 + 二分（灵巧的回溯探针）
既然 DAG 无环，那递归天然就是安全的——不用担心无限套娃，因为没有环可以绕回去。
路径天生有序，递归回溯就能把每条边捋一遍。而且 n 的范围不算太大，记忆化搜索正好派上用场：从终点倒推，一路回溯，把中间结果缓存下来，既省堆又省脑细胞。
思路也很直球：定义 dfs(u) 表示从节点 u 出发，在只允许边成本 ≥ limit 的条件下，到达终点 n-1 所需的最小总花费。
你从 0 开始递归，对于当前节点 u：
- 如果
u恰好是终点，那就不用再花一分钱，返回0； - 否则，遍历
u的所有出边(v, cost)，只挑cost >= limit的硬边走，递归计算dfs(v)，加上当前边的成本cost，取所有结果中的最小值； - 用
@cache装饰器自动缓存每个u的计算结果——这样每个节点最多算一次，后面的递归直接复用。
最后，如果 dfs(0) <= k，说明阈值 limit 可行。
整个过程就像从终点往回铺路标：你只关心"从当前位置到终点最少花多少钱"，而每个子问题结构相同，递归套娃加上缓存，把"反向推导"玩成了自动化流水线。时间复杂度O(m)（每条边最多被访问一次），乘上二分的O(log C)，总复杂度O(m log C)——比 Dijkstra 省掉了整个堆操作的log n，轻快得像卸了甲的轻骑兵。
# 解法二：记忆化搜索
def check(limit: int) -> bool:
@cache
def dfs(u: int) -> int:
if u == n-1:
return 0
ans = float('inf')
for v, cost in g[u]:
if cost >= limit:
ans = min(ans, dfs(v) + cost)
return ans
return dfs(0) <= k
你舞着这把递归匕首，咧开的嘴角还没来得及合上，脑子里突然闪过一个声音：“递归深度告警。” 没错，万一哪天数据规模翻倍，你的递归栈就可能当场爆掉，留下一地 RecursionError 的碎片。
作为一名成熟的特工，你习惯把命运攥在自己手里——与其依赖黑盒子的调用栈，不如自己动手排兵布阵，勤劳迭代。于是，你收起匕首，抽出第三把武器——拓扑排序 + DP。
拓扑排序 DP + 二分（终极流水线探针）
拓扑排序是 DAG 的天选搭档。它能把所有节点排成一条流水线，保证每个节点轮到它的时候，所有前驱都已经处理完毕。这意味着你可以顺着流水线一路往前递推，不需要堆来排序，不需要递归来回溯，一个普通队列就搞定。
它和记忆化搜索，本质上是同一道递推公式的两面：
- 记忆化是 “拉”：dfs(u) 向后继节点要答案，一层层往下问，答案再一层层往回传；
- 拓扑排序是 “推”：dp[u] 算完直接塞给后继节点，按拓扑序从前往后走，接力棒一样往下传。
区别在于——“谁先算谁后算"这件事，记忆化靠递归栈隐式决定，拓扑排序靠入度归零机制显式决定——入度归零的先上，处理完它的后继，后继入度减一，新的归零节点跟上。整个顺序由 DAG 的结构天然锁定，比递归栈靠谱得多，也比堆排序轻快得多。
不过开工前有个小坑要填：图中可能存在一些不可达的"孤岛节点”——入度为 0 但不是起点，没有任何边指向它们，从起点绝对到不了。这些孤岛如果留着，它们的后继会一直等不到入度归零，整条链路直接卡死。所以先做一轮预处理，把这些坏死组织清理干净：
def findMaxPathScore(edges: List[List[int]], online: List[bool], k: int) -> int:
n = len(online)
g = [[] for _ in range(n)]
l, r = float('inf'), 0
deg = [0] * n # 记录节点入度
for u, v, cost in edges:
if not online[u] or not online[v]:
continue
g[u].append((v, cost))
r = max(r, cost)
l = min(l, cost)
deg[v] += 1 # 更新节点入度
# 阈值探针!
# 先预处理：剥离从起点不可达的"孤岛节点"
q = deque([i for i in range(1, n) if deg[i] == 0]) # 入度为 0 且不是起点的节点
while q:
u = q.popleft() # 弹出一个孤岛
for v, _ in g[u]:
deg[v] -= 1 # 孤岛的后继入度减 1
if v and deg[v] == 0: # 后继也变成孤岛了（且不是起点）
q.append(v) # 加入剥离队列
def check(limit: int) -> bool:
# todo: 检查阈值 limit 是否可行
pass
# 二分答案
......
剥完之后，剩下的 deg 就是一份干净的、只保留从起点可达结构的入度表。
接下来 check(limit) 就清爽了，三步走：
初始化：复制入度表
cdeg = deg.copy()，dp数组全填无穷大，初始化dp[0]=0，队列只放起点0；为什么要 deg.copy()？因为 check 里的拓扑排序是破坏性的——每处理一个节点就 cdeg[v] -= 1，跑完一次 check 后整个入度表就全被减成 0 了。但二分要调几十次 check，每次都需要一份完整的、初始状态的入度表。所以每次都得 copy 一份新的来"消耗"。
流水线推进：弹出节点
u，如果是终点n-1，直接返回dp[u] <= k——此时所有前驱都已处理完毕；松弛 + 传递：遍历
u的出边，只走cost >= limit的硬边做松弛，更新dp[v]。注意：不管边够不够硬，cdeg[v]都要减一——边权过滤管的是dp值，入度递减管的是拓扑序，两条线互不干扰。入度归零的节点入队，轮到它上场。
时间复杂度 O(m) 一次检查，套上二分O(log C)，总复杂度 O(m log C)。无递归、无堆栈、遇终点提前宣判——DAG 上的性能天花板。
def findMaxPathScore(edges: List[List[int]], online: List[bool], k: int) -> int:
n = len(online)
g = [[] for _ in range(n)]
l, r = float('inf'), 0
deg = [0] * n # 记录节点入度
for u, v, cost in edges:
if not online[u] or not online[v]:
continue
g[u].append((v, cost))
r = max(r, cost)
l = min(l, cost)
deg[v] += 1
# 阈值探针!
# 预处理：剥离从起点不可达的"孤岛节点"
q = deque([i for i in range(1, n) if deg[i] == 0])
while q:
u = q.popleft()
for v, _ in g[u]:
deg[v] -= 1
if v and deg[v] == 0:
q.append(v)
def check(limit: int) -> bool:
dp = [float('inf')] * n # dp[i]: 从起点到 i 的最小总花费
cdeg = deg.copy() # 拷贝入度——拓扑排序会消耗它，不能动原件
dp[0] = 0
q = deque([0])
while q:
u = q.popleft()
if u == n - 1:
return dp[u] <= k # 到达终点，提前宣判！
for v, cost in g[u]:
if cost >= limit:
dp[v] = min(dp[v], dp[u] + cost) # 松弛：只走够硬的边
cdeg[v] -= 1 # 入度必减——跟边权无关，这是拓扑序的事
if cdeg[v] == 0: # 前驱全部处理完毕，轮到 v 上场
q.append(v)
return False
# 二分答案
......
尾声
探针归位，二分收敛——这是你第无数次看着二分框架优雅地合拢，像狙击镜里十字准星缓缓锁住目标。
Dijkstra 重剑无锋，记忆化匕首如风，拓扑排序流水线降维打击——三连击打完收工，最终撑起整个猎杀框架的，还是那招最朴素的祖传手艺——二分：把一个"既要又要"的双约束难题，劈成一道道简单的判断题：“够不够？行不行？能还是不能？”
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。