lessons/课程/12-历年真题/01-2016至2018期望最短路与基环建模.md

2016–2018 真题：期望状态、近最短路计数与基环搜索

本节目标

通过三年提高组真题，学习如何从随机事件保留最小充分状态、把“比最短路多 K”改写为松弛余量，以及利用 $m\le n$ 把一般图搜索压成树/基环树。

前置知识与课前自测

前置：Floyd、概率期望、动态规划、Dijkstra、基环树、字典序。

1. 两个相邻时段都申请换教室时，期望路程为何有四种组合？
2. 边 $u\to v$ 相对最短路多出的代价怎样定义才保证非负？
3. 连通图满足 $m=n$ 时，为何删除环上一条边后得到树？

答案

1. 两次申请是否成功独立，各有原/新教室两种结果。 2. $\Delta=dist[v]+w-dist[u]\ge0$，其中 dist 是到终点最短距离。 3. 连通 n 点 n 边恰有一个环；删环边后连通且边数 n-1。

问题动机与共同考虑链

三题表面分别是概率、路径计数、字典序搜索，但共同点是题面给了“只偏离基础结构一点”的限制：申请状态只有两种、允许长度只比最短路多 K、边数只比树多一条。深度来自找到这个小偏离量，而不是上更重模板。

精选例题 1：NOIP 2016 换教室

来源、题意与范围

• 洛谷-P1850 换教室，NOIP 2016 提高组 D1T3
• $n,m\le2000$，教室数 $v\le300$；至多申请 m 节，每次独立以 $k_i$ 成功，最小化相邻课程移动体力的期望。

Hint 1：图先处理什么

移动时总走最短路，先 Floyd 得到任意教室距离。

Hint 2：DP 状态为何需要最后一维

下一段期望取决于当前时段是否申请，而不只取决于已申请次数。

Hint 3：两端都申请

枚举前后申请成功/失败四种组合，以概率乘对应最短距离。

Observations

• 若直接枚举申请集合有 $2^n$ 种；但总期望是相邻时段贡献之和，只需保留上一时段的申请决策。
• 申请结果不能在学期中观察后再决定，DP 决策是“申请与否”，随机结果只进入转移期望。
• 图本身不随课程变化，Floyd 的 $v^3$ 与课程 DP 的 $nm$ 可分离。

Editorial

令 dp[i][j][s] 为前 i 个时段申请 j 次、第 i 节是否申请为 s 时的最小期望。s=0 时当前教室确定为 $c_i$；s=1 时以 $1-k_i,k_i$ 位于 $c_i,d_i$。从上一状态转移时计算两个随机位置间距离期望。

正确性证明

状态包含未来所需的全部信息：申请次数约束与上一课程位置分布。期望的线性性允许把总路程拆成相邻段期望之和；独立申请保证四种联合概率为乘积。对最后一节申请/不申请和所有不超过 m 的次数取最小，覆盖全部预先申请方案且不重复决策。

复杂度 $O(v^3+nm)$，空间滚动后 $O(m)$；附件保留二维时序便于阅读。

核心伪代码与附件

distance = Floyd(classroom_graph)
dp[1][0][not_apply] = 0
dp[1][1][apply] = 0
for i = 2..n:
    for used = 0..m:
        transition from previous apply flag
        edge_cost = expectation over previous/current classroom distributions
answer = min(dp[n][used][flag] for used <= m)

完整 C++17 附件

精选例题 2：NOIP 2017 逛公园

来源、题意与范围

• 洛谷-P3953 逛公园，NOIP 2017 提高组 D1T3
• 有向非负权图，$N\le10^5,M\le2\times10^5,K\le50$；统计 1 到 N、长度不超过最短路加 K 的路线数模 P；无穷多输出 -1。

Hint 1：从终点反向最短路

计算每点到 N 的 dist，才能评价一条边偏离最短路多少。

Hint 2：新状态

状态 `(u,e)` 表示从 u 出发还允许比 dist[u] 多花 e。

Hint 3：无穷来自哪里

只有松弛余量为 0 的环能在不消耗 K 的情况下无限重复。

Observations

• 直接按总长度 DP，边权与最短路可达 $10^8$；改用额外代价后维度只有 K+1。
• 对边 $u\to v$，$\Delta=dist[v]+w-dist[u]\ge0$ 是三角不等式留下的“非最短损失”。
• 正权/正余量环最多走有限次；零余量环若从当前状态可达且还能到终点，就产生无限路线。

Editorial

反图 Dijkstra 求 dist。记忆化搜索 solve(u,e)：可以在 u=N 时结束贡献 1；对每条边，若 delta 不超过 e，则转移到 (v,e-delta)。用三色状态标记未访问、递归栈中、已完成；再次进入栈中同状态说明零余量环，答案无限。

正确性证明

任一路线长度减 dist[u] 等于沿途各边 delta 之和，望远镜消去中间 dist，因此路线合法当且仅当总 delta 不超过 K。递归逐边消耗 delta，与路线一一对应。状态环要求额外维度不变，而 delta 非负，所以环上全为 0；它可任意重复并最终沿有限 dist 路到 N，充要地给出无穷。

状态数 $O(NK)$，转移总量 $O(MK)$，另有 Dijkstra $O(M\log N)$。

核心伪代码与附件

dist = Dijkstra(reverse_graph, source=N)
solve(u, extra):
    if state[u][extra] is active: infinite
    answer = 1 if u == N else 0
    for edge u->v:
        delta = dist[v] + edge.weight - dist[u]
        if delta <= extra: answer += solve(v, extra-delta)

完整 C++17 附件

精选例题 3：NOIP 2018 旅行

来源、题意与范围

• 洛谷-P5022 旅行，NOIP 2018 提高组 D2T1
• 连通简单无向图 $n\le5000$，且 $m=n-1$ 或 $m=n$；从 1 按 DFS 式旅行访问所有城市，最小化首次访问序列字典序。

Hint 1：树上答案

邻接点升序 DFS 就是字典序最小序列。

Hint 2：多一条边

基环图的合法 DFS 生成树等价于删掉环上一条边。

Hint 3：规模允许什么

$n=5000$，可以枚举删边并重跑 DFS。

Observations

• 一般图枚举生成树不可行，但 $m\le n$ 把环数限制为 0 或 1。
• 给定一棵树后，当前可选新城市取编号最小不会损害后续更早位置，升序 DFS 最优。
• 枚举所有边也安全：删非环边会不连通，用遍历长度直接淘汰，无需先显式找环。

Editorial 与证明

邻接表排序。树情形直接 DFS。基环情形枚举禁止每条边，忽略它 DFS；只有删环边能访问全部 n 点。所有可能 DFS 生成树都由删一条环边得到，因此候选全集完整；取序列字典序最小即答案。

复杂度 $O(n(n+m))=O(n^2)$，对 5000 约数千万次访问。

核心伪代码与附件

sort every adjacency list
if m == n-1: answer = DFS_order(ignore_none)
else:
    for each edge e:
        candidate = DFS_order(ignore=e)
        if candidate visits all vertices: answer = lexicographic_min(answer,candidate)

完整 C++17 附件

实现指南

三题分别容易错在期望维度、零环与候选环边管理。《换教室》滚动数组要在每层整体重置为无穷大；《逛公园》必须先判定最短路相关子图中是否存在可重复零代价环；《旅行》枚举删环边时应保留原边编号，避免对重边或无向边两个方向删错。调试时优先与状态枚举/删边 DFS 对拍，而不是只比较最终答案。

扩展与联系

三题分别展示“随机性只增加一位状态”“最短路只增加 K 余量”“树只增加一条环边”。遇到高维表象时，先寻找相对基准结构的小偏差参数。

总结与自检

1. 换教室状态为何不需记录更早申请结果？
2. 逛公园 delta 求和为何等于路线长度减 dist？
3. 哪类环导致无限路线？
4. 旅行为何能枚举删边而一般图不能？

课后训练建议

三题均建议先写对应小规模暴力：枚举申请集合、限制步数枚举路线、枚举所有 DFS 决策；再与附件随机对拍。