lessons/课程/05-最短路与类最短路/03-最短路树次短路与差分约束.md

类最短路：最短路树、严格次短路与差分约束

本节目标

学完后，你应能在最短距离之外优化前驱树，维护每点前两种不同到达长度，并把形如 $x_v-x_u\le c$ 的约束转成有向边，理解“求最大值却跑最短路”的对偶含义。

前置知识与课前自测

前置：Dijkstra、树、Bellman-Ford、负环。

1. 每个点任选一条满足 dist[u]+w=dist[v] 的边，是否一定形成树？需要什么边权条件？
2. “第二短”是否把另一条与最短路等长的路线算进去？
3. 约束 $x_B-x_A\ge D$ 怎样改写成 <= 形式？

自测答案

1. 正权时距离沿父边严格下降，必回到源且无环；零权时可能形成等距环，需额外处理。 2. 依题意。本节 `Roadblocks` 要求长度严格大于最短路，等长不同路线不算。 3. $x_A-x_B\le-D$，建边 $B\to A$ 权 $-D$。

问题动机

“类最短路”并非换一个模板，而是仍使用松弛语言处理不同目标：

• 距离固定后，在所有最短前驱中选附加代价最小者；
• 每个点保留两个不同距离标签；
• 把不等式的传递上界看作路径权和。

关键是明确标签语义、比较顺序和能丢弃哪些候选。

核心知识与实现指南

• 多目标比较要先固定主目标：只有主距离相等时才比较父边权。
• 多标签最短路必须明确“等长是否算不同一档”；本节次短标签使用严格不等式。
• 差分约束统一成 x_v <= x_u + c 后再建边，负号和方向同时从公式读取。
• 负边图不能使用 Dijkstra；规模允许时，确定性的 Bellman-Ford 比未经证明的 SPFA 复杂度更可靠。

精选例题 1：Paths and Trees

来源信息与题意

• VJudge：CodeForces-545E Paths and Trees
• 原题：Codeforces Round 303 (Div. 2)
• 难度：2000；考点：最短路树、相等距离的次级目标

连通简单带权无向图有 $n,m\le3\times10^5$、正权至 $10^9$，给源点 $s$。在保持 $s$ 到每点距离都与原图最短距离相同的生成树中，最小化树边权总和，并输出边编号。

Hint 1

先求距离；对每个 $v\ne s$，父边必须满足 `dist[u]+w=dist[v]`。

Hint 2

正权使父亲距离严格小于儿子，所以各点独立选父边不会成环。

Hint 3

Dijkstra 松弛距离相等时，若新边权更小，只替换父边，不必重新入堆。

Observations、Editorial 与证明

对每个非源点，从所有最短前驱边中选权值最小者。由于权值为正，沿父边距离严格下降，最终到源点且不成环；每点恰一条父边，因此组成生成树。任一最短路树也必须为每点选一条最短前驱边，而总权是这些独立选择之和，所以逐点取最小达到全局最小。

Dijkstra 中严格变短时更新距离和父边；相等时只比较父边权。复杂度 $O((n+m)\log n)$。

核心伪代码与参考实现附件

run Dijkstra from source
on shorter distance to v: replace distance and parent edge
on equal distance: replace parent edge only if its own weight is smaller
because all weights are positive, chosen parents strictly decrease distance
output sum and IDs of one chosen parent edge for every non-source vertex

完整 GNU C++17 参考实现见附件：CodeForces-545E.cpp

复盘与变式

若有零权边，逐点独立选最小父边可能在同距离点之间成环；需在等距零权子图中额外构造连向较小距离层的森林。

精选例题 2：Roadblocks

来源信息与题意

• VJudge：POJ-3255 Roadblocks
• 原来源：USACO 2006 November Gold
• 大致难度：提高；考点：每点两标签、严格次短路

无向正权图有 $N\le5000,R\le10^5$，边权 $1..5000$。求 1 到 $N$ 的严格第二短路线长度；路线允许重复经过边和点。若有多条等长最短路，它们仍只占“最短长度”这一档。

Hint 1

为每点维护最短 `first[v]` 与严格更大的次短 `second[v]`。

Hint 2

候选比最短还小时，先把旧最短交换出来，它仍可能更新次短。

Hint 3

只有 `first[v] < candidate < second[v]` 才更新次短；等于最短的候选丢弃。

Observations、Editorial 与证明

优先队列中的标签既可能是最短也可能是次短。松弛到 $v$ 时，若候选成为新最短，把旧最短继续作为次短候选；否则仅在严格介于两者时更新次短。

任一到达 $v$ 的第三种或更长标签，后接任意正权后缀仍不可能优于从同点的前两种标签接该后缀，所以可丢弃。目标点的第二标签即全局严格第二短。复杂度 $O((N+R)\log N)$。

核心伪代码与参考实现附件

first[source] = 0; second[*] = infinity
pop a distance label d at u
for edge u-v:
    candidate = d + weight
    if candidate < first[v]: swap(candidate, first[v]); push first[v]
    if first[v] < candidate < second[v]: set and push second[v]
output second[destination]

完整 GNU C++17 参考实现见附件：POJ-3255.cpp

复盘与变式

若题目禁止重复点，变成简单路径的第二短问题，不能直接使用本算法；允许回走是两标签支配性成立的重要背景。

精选例题 3：Layout

来源信息与题意

• VJudge：POJ-3169 Layout
• 原来源：USACO 2005 December Gold
• 大致难度：省选入门；考点：差分约束、负环、无上界

$2\le N\le1000$ 头牛按编号顺序站在数轴上，允许重合。至多 $10^4$ 条喜欢约束要求 $A,B$ 距离不超过 $D$，至多 $10^4$ 条讨厌约束要求距离至少 $D$，$A<B$。求满足约束时 $x_N-x_1$ 的最大值；无解输出 -1，无上界输出 -2。

Hint 1

统一写成 `x_v <= x_u + c`，对应边 `u -> v` 权 `c`。

Hint 2

编号顺序给出 `x_i <= x_{i+1}`，即边 `i+1 -> i` 权 0。

Hint 3

喜欢：`A->B (D)`；讨厌：`B->A (-D)`。

Hint 4

任意路径给出 $x_N-x_1$ 的上界，最紧上界是 1 到 N 的最短路；负环表示约束矛盾，不可达表示没有上界。

Observations

1. 最短路不是在计算实际走路，而是在传递“变量最多是多少”的上界。
2. 从 1 不可达的负环仍会让整个约束系统无解，所以要先用所有点为源检测全局负环。
3. “最大可行距离”由所有上界中最紧者决定，因此数值上是最短路径。

Editorial 与证明

建立差分约束图。先把所有距离初始化为 0，做 $N$ 轮 Bellman-Ford；第 $N$ 轮仍能松弛则有负环，沿环相加得到 $0<负数$ 的矛盾，输出 -1。

再令 dist[1]=0、其余无穷，做至多 $N-1$ 轮松弛。每条从 1 到 $N$ 的路径都推出 $x_N-x_1\le$ 路径权，故最短路是最紧上界；无负环时最短距离标签本身满足所有可达约束，未达变量可平移安排，所以上界可达。若 $N$ 不可达，没有任何约束链限制两者距离，输出 -2。

边数不超过约 $2.1\times10^4$，确定性的 Bellman-Ford 为 $O(NE)$。先用 $N$ 轮从超级源检测全局负环（约 $2.1\times10^7$ 次松弛），再用 $N-1$ 轮求最短路（约 $2.1\times10^7$ 次松弛），合计约 $4.2\times10^7$ 次，可接受。

核心伪代码与参考实现附件

convert every constraint to x[v] <= x[u] + weight and add edge u->v
add order edges (i+1)->i with weight 0
if Bellman-Ford from a super-source finds a negative cycle: output -1
dist = Bellman-Ford(source=1)
if N is unreachable: output -2
else: output dist[N], the tightest upper bound on x[N]-x[1]

完整 GNU C++17 参考实现见附件：POJ-3169.cpp

复盘与变式

若要求一组具体坐标，可从可行势能恢复并整体平移；若额外规定 $x_1=0$ 且所有变量有上下界，把这些边一并加入超级源系统即可。

高阶扩展：01 Balanced——最优字符串其实是最短路距离

来源信息、题意与范围

• VJudge：AtCoder-agc056_c 01 Balanced
• 原题：AtCoder Grand Contest 056 C
• 官方难度口径：900 分；考点：前缀势能、差分约束、0-1 BFS、奇偶收紧

构造长度 $N$ 的 01 串。每个条件 $[L_i,R_i]$ 要求其中 0、1 数量相等；输出满足全部条件的字典序最小串。$2\le N\le10^6$，$1\le M\le2\times10^5$，区间长度均为偶数，题目保证有解。

Hint 1：把字符改写成前缀高度

令 0 贡献 $+1$、1 贡献 $-1$，$v_i$ 为前 $i$ 位之和。区间平衡等价于 $v_{L_i-1}=v_{R_i}$。

Hint 2：先把等于 1 放宽成至多 1

相邻前缀原本要求 $|v_i-v_{i-1}|=1$。暂改成 $\le1$，再问在 $v_0=0$ 下每个 $v_i$ 最大能有多大。

Hint 3：上界为什么是最短路

相邻位置连权 1 双向边，等式端点连权 0 双向边。任一路径都给出 $v_x\le v_0+\operatorname{len(path)}$，最紧上界就是从 0 出发的最短距离；整组最短距离本身满足全部差分约束。

Observations

1. 逐位尝试 0 再做可行性检查需要 $N$ 次全局判定；前缀和把字典序目标变成按顺序最大化 $v_1,v_2,\ldots$。
2. 等式不是额外 DP 状态，而是零代价边；相邻变化至多 1 是单位边。最大可行势能恰等于最短路给出的最紧上界。
3. 放宽后看似可能出现相邻高度相等，但位置 $i$ 的前缀高度奇偶固定为 $i$。所有零边连接同奇偶位置，所以最短距离也保留该奇偶；相邻距离差至多 1 且奇偶不同，只能恰差 1。

Editorial、证明与复杂度

定义

$$ v_i=#0(s_1\ldots s_i)-#1(s_1\ldots s_i),\qquad v_0=0. $$

字典序更小意味着在第一个不同位置选择 0，即让对应前缀高度更大，因此要字典序最大化向量 $(v_1,ldots,v_N)$。建 $N+1$ 点图：$i-1\leftrightarrow i$ 权 1；每个条件 $L_i-1\leftrightarrow R_i$ 权 0。任意可行 $v$ 都满足每条边 $v_y\le v_x+w$，所以 $v_i\le\operatorname{dist}(0,i)$。另一方面，最短距离满足三角不等式，故把 $v_i$ 取为距离可同时达到每个点的最大上界。

零边连接下标差为偶数的点，单位边改变一次下标奇偶，所以任意从 0 到 $i$ 的路长度奇偶与 $i$ 相同，最短距离亦同。于是相邻距离不能相等，只能相差 1；放宽解自动回到合法 01 串。若 $vi=v{i-1}+1$ 输出 0，否则输出 1。图边权只有 0/1，用 0-1 BFS，时间 $O(N+M)$、空间 $O(N+M)$，可承受 $N=10^6$。

核心伪代码、边界与附件

for i in 1..N: add bidirectional edge (i-1, i, weight=1)
for condition (L, R): add bidirectional edge (L-1, R, weight=0)
dist = zero_one_BFS(source=0)
for i in 1..N:
    answer[i] = '0' if dist[i] > dist[i-1] else '1'

不能把 0/1 字符值直接当边权；图上距离表示的是“高度最大上界”。内存上用紧凑邻接表更稳，附件的 vector 写法在题目 1024 MiB 限制内仍可通过。完整 GNU C++17 附件：AtCoder-agc056_c.cpp

复盘与变式

核心迁移是“最大化满足 Lipschitz 约束的势能 = 从锚点出发的最短距离”。若区间长度允许为奇数，零边可能连接异奇偶位置，放宽解未必满足相邻差恰为 1，必须重新处理可行性，不能照搬结论。

灵活性实验室：Walk Around Neighborhood

来源与为什么放在本章

• VJudge：AtCoder-agc062_d Walk Around Neighborhood
• 原题：AtCoder Grand Contest 062 D
• 官方难度口径：1100 分；$N\le2\times10^5$，所有偶数步长 $2\le D_i\le2\times10^5$

每次任选一个未用步长 $d$，在平面上移动恰好曼哈顿距离 $d$；用完后回原点，并最小化途中到原点曼哈顿距离的最大值。它不要求跑 Dijkstra，因此不占“最短路算法”正式名额；保留在此是为了训练删状态：二维坐标最终只需其到原点的距离 $R$。

关键观察 1：两个半径之间何时能走一步

从半径 $R$ 的任一点走距离 $D$ 到半径 $R'$ 的某点，充要条件是 $|R-R'|\le D\le R+R'$。曼哈顿圆周的连续性保证区间内每个 $D$ 都能实现。

关键观察 2：固定顺序与上界 K

前缀距离未触及 $K$ 前只能向外积累，后缀同理。第一次到达半径 $K$ 的步与最后一次离开半径 $K$ 的步给出两个局部三角不等式；中段所有 $D_i\le2K$ 时可以一直停留在半径 $K$ 的圆周上。

关键观察 3：允许重排后为什么出现部分和

当最大步长 $M>K\ge M/2$ 时，需要在两个大步长前分别垫入一些不超过 $K$ 的小步长，使局部三角不等式成立。最优选择归结为某个部分和是否落入区间 $[A-K,\ S-(B-K)]$。

不做题也应带走的 Editorial 主线

先用总和 $S<2M$ 排除无解，这是闭合折线的三角不等式。固定答案上界 $K$ 后，状态不是坐标集合，而是可达半径集合；上面的充要条件使它保持为连续区间。若 $K\ge M$ 总能安排；否则只需考虑 $M/2\le K<M$，挑出大于 $K$ 的两个最小值 $A,B$，小值部分和要同时为两端提供“缓冲”。当小值总和足够大，升序贪心跨过下界时不会越过上界；只有总和 $O(M)$ 的困难区间需要按值频数做有界部分和。结合答案二分可做到官方给出的 $O(M\sqrt M)$ 量级。

这道题的失效边界很重要：若距离换成离散障碍图上的最短路，半径相同的点不再等价，可达集合也未必连续；此时不能把坐标删成一个 $R$。本题作为阅读实验室，不设为后续硬前置，也不声称附件已完成。

扩展与联系

• 最短路 DAG 上可计最短路条数、判必经边；有零权边时先处理等距环。
• 第 $k$ 短路线不能为每点简单保留固定两个标签；通常需 A*、可持久化堆或专门的 k-shortest 算法，并明确是 walk、trail 还是 simple path。
• 差分约束与势能重标号相连：无负环时，最短距离是一组满足三角不等式的势能。

总结与自检

1. 最短路树中相等距离时优化了什么？为何可逐点独立？
2. 次短标签为何必须严格大于最短标签？
3. 第三到达标签为何不会产生目标的第二短路线？
4. 差分约束的边方向怎样从公式读出？
5. 为什么最大可行差值等于最短路径上界？

课后训练建议

第一题对拍所有小图生成树，确认总权最小；第二题用允许回走的朴素优先队列枚举前若干路径长度对拍；第三题每条约束先手写不等式再建边，禁止靠背方向。复盘分别记录三个标签的语义：距离、父边权、第一/第二距离、变量上界。