「重建」题解

题意简化

给定无向连通图 $G$，每条边有长度 $w_i$。
关键点集合 $A$（包含 $s$ 和 $t$）。
给所有边同时加上一个非负整数 $c$ 后，要求：

1. $s$ 到 $t$ 的全局最短路长度
2. 等于 $s$ 到 $t$ 且只能经过关键点的最短路长度（关键点路径上所有点必须在 $A$ 中）

求最大的 $c$，或判断：

• 不可能：输出 Impossible
• 可以无限大：输出 Infinity

$n \le 1000$，$m \le 10000$。

核心观察

1. 关键点路径限制

只能经过关键点的路径：所有中间节点必须是 $A$ 中的点。
这意味着路径可以表示为：$s \to a_1 \to a_2 \to \dots \to t$，其中每个 $a_i \in A$。

2. 加 $c$ 的影响

每条边都加 $c$，那么：

• 任意长度为 $L$ 的路径，新长度为 $L + c \times (\text{边数})$
• 边数 = 路径经过的边数

关键思路：比较两类路径

设：

• $d_1(x,y)$：$x$ 到 $y$ 的全局最短路长度（原图）
• $d_2(x,y)$：$x$ 到 $y$ 的只走关键点的最短路长度（如果不可达则为 $\infty$）

加 $c$ 后，路径 $P$ 的新长度 = 原长度 + $c \times |P|$（$|P|$ 是边数）。

我们需要：

$$\min_{\text{全局路径 }P} \left[ d_1(P) + c \times |P| \right] = \min_{\text{关键点路径 }Q} \left[ d_2(Q) + c \times |Q| \right] $$

解法：二分答案

1. 可行性判断

对于给定的 $c$，检查上述等式是否成立。

令：

• $f(c) = \min_{P} [d_1(P) + c|P|]$（全局最短路）
• $g(c) = \min_{Q} [d_2(Q) + c|Q|]$（关键点最短路）

要求 $f(c) = g(c)$。

2. 计算 $f(c)$ 和 $g(c)$

由于每条边权重从 $w$ 变为 $w+c$，可以：

• 在新图上跑最短路：边权为 $w_i + c$
• $f(c)$ = $s$ 到 $t$ 的新图最短路
• $g(c)$ = 在只包含关键点 $A$ 的诱导子图上跑最短路（边权同样加 $c$）

但 $g(c)$ 需要在关键点子图上计算，而关键点之间可能通过非关键点连接？
不，关键点路径要求所有中间点都是关键点，所以只能在关键点之间直接有边时才能走。

3. 预处理关键点间距离

提前计算：

• 对于每对关键点 $u,v \in A$，计算全局最短距离 $dist[u][v]$ 和对应边数 $edges[u][v]$
• 那么在加 $c$ 后，$u \to v$ 的新距离 = $dist[u][v] + c \times edges[u][v]$

关键点子图：完全图，边权为 $(dist[u][v], edges[u][v])$ 对。

4. 二分 $c$

由于 $c$ 最大可能很大，但答案有单调性：

• 如果 $c$ 可行，那么更小的 $c$ 也可能可行？
  不一定，需要分析。

实际上，$f(c)$ 和 $g(c)$ 都是关于 $c$ 的线性分段函数（斜率是最短路径的边数）。

我们要求 $f(c) = g(c)$ 的最大 $c$。

算法步骤

1. 预处理

   • 在原图上跑全源最短路，得到每对点间的距离和边数
   • 提取关键点集合 $A$，构建关键点完全图：
     • 边 $(u,v)$ 的权值 = $(dist[u][v], edges[u][v])$

2. 计算函数

   • $f(c)$：在全局图上，$s$ 到 $t$ 的最短路 = $\min_{P} [dist(P) + c \times edges(P)]$
   • $g(c)$：在关键点图上，$s$ 到 $t$ 的最短路 = $\min_{Q} [dist(Q) + c \times edges(Q)]$

   这两个都是分段线性凸函数（斜率递增）。

3. 求解 我们需要最大的 $c$ 使得 $f(c) = g(c)$。

   方法：

   • 求出两个函数的所有分段点（斜率变化点）
   • 比较两个函数，找到最后一个交点
   • 如果没有交点 → Impossible
   • 如果在某个点之后一直相等 → Infinity

4. 实现 由于 $k = |A| \le n \le 1000$，可以：

   • 枚举所有可能的路径边数（$1$ 到 $n-1$）
   • 对于每个边数 $e$，计算 $f_e = \min_{|P|=e} dist(P)$（全局最小距离）
   • 同理计算 $g_e$（关键点路径）
   • 那么 $f(c) = \min_e [f_e + c \times e]$
   • $g(c) = \min_e [g_e + c \times e]$

   然后比较这两个下凸包。

复杂度

• 全源最短路：$O(nm\log n)$ 或 $O(n^3)$
• 构建凸包：$O(n^2)$
• 求交点：$O(n)$
• 总复杂度可接受

关键点

• 将加 $c$ 转化为路径的线性函数
• $f(c)$ 和 $g(c)$ 是分段线性凸函数
• 比较两个凸包求最大交点
• 注意 Impossible 和 Infinity 的情况