1. 从一道图论题看差值排序的实战价值CodeForces 1307D 这道题第一次看到的时候我盯着题面愣了几分钟。题目大意是给定一张无向连通图其中有 k 个特殊点你可以在任意两个特殊点之间加一条边问加完这条边之后从起点 1 到终点 n 的最短路最大是多少。注意是最大——你要选一对特殊点连边使得最终的最短路尽可能长。这个设定本身就很有意思。大多数人做最短路问题的惯性思维是怎么让路径更短而这道题反着来让你在有限的自由度里尽量让最短路不要被压得太狠。我第一次做的时候直接想暴力枚举所有特殊点对跑 k² 次 BFS结果一看数据范围就知道凉了——k 可以到 2×10⁵边数也是 2×10⁵ 级别平方复杂度直接爆炸。后来看了题解才明白这题的核心突破口在于一个非常巧妙的转化加边之后的新最短路要么是原来的最短路加边没起作用要么是经过这条新边的路径。而经过新边的路径长度可以表示为d1[u] 1 dn[v]或者反过来其中d1是从起点 1 出发的最短距离dn是从终点 n 出发的最短距离。于是问题就变成了在 k 个特殊点中选两个点 u 和 v使得min(d1[u] dn[v], d1[v] dn[u]) 1尽可能大同时还要和原最短路取 min。到这里问题的关键就落在了怎么高效地处理这个选两个点使得某个表达式最大上。而差值排序这个技巧就是解决这类问题的利器。它的核心思想是通过排序消除 min/max 中的对称性把二维的枚举问题降成一维的扫描问题。我写这篇文章不只是想讲这道题的解法更想借这道题把差值排序这个技巧彻底讲透。因为在实际的算法竞赛和工程问题中这类选两个元素优化某个组合表达式的场景非常常见掌握了这个套路你能解决一大类看起来毫无头绪的题目。不管你是刚接触图论的新手还是已经刷了几百道题想突破瓶颈的老手这篇文章都会给你一些实实在在的东西。2. 把题目翻译成人话加一条边最短路最大能是多少2.1 题目条件的精确理解先把题意掰开揉碎说清楚。给你一张 n 个点、m 条边的无向连通图边权全部为 1。再给你 k 个特殊点这些点是图中普通的点只是被标记出来了。你现在可以在任意两个特殊点之间加一条边边权也是 1加完之后从 1 号点到 n 号点的最短路会变成多少你要选一对特殊点使得这个最短路尽可能大输出这个最大值。注意几个容易读错的点你只能加一条边而且这条边的两个端点必须都是特殊点。加边之后原来的边都还在新边只是多了一条。你要最大化的是加边之后 1 到 n 的最短路不是最小化。如果加边之后最短路没有变化比如加的边根本不在任何最短路上那答案就是原图的最短路。为什么这个最大化的设定是合理的因为在实际场景中你可以理解为你是一个破坏者你想让从 1 到 n 的通信尽可能慢但你只能在一个受限的操作空间里只能在特殊点之间加边做手脚。加边本来应该让路更短但你要选一对点使得这个缩短效果最小。2.2 为什么暴力枚举一定会超时最直接的想法枚举所有特殊点对 (u, v)加边然后跑一次 BFS 求最短路取最大值。特殊点有 k 个点对数量是 k(k-1)/2每次 BFS 是 O(nm)。总复杂度 O(k²(nm))k 和 n 都是 2×10⁵ 级别这个复杂度是天文数字连样例都跑不过去。稍微优化一点其实不需要每次重新跑 BFS。我们可以先预处理出从起点 1 到所有点的最短距离d1[]以及从终点 n 到所有点的最短距离dn[]。这两个数组各跑一次 BFS 就能得到复杂度 O(nm)。有了这两个数组之后对于任意一对特殊点 (u, v)加边之后经过这条新边的最短路径长度就是min(d1[u] 1 dn[v], d1[v] 1 dn[u])而加边之后的全局最短路就是min(原最短路, 上面这个值)所以我们只需要在 k 个特殊点中找一对 (u, v)使得min(d1[u] dn[v], d1[v] dn[u])最大。这样就把 BFS 的次数从 k² 次降到了 2 次但枚举点对仍然是 O(k²)还是过不了。2.3 问题的数学本质一个 min 形式的组合优化现在问题变得纯粹了给定 k 个点每个点 i 有两个属性a_i d1[i]和b_i dn[i]你要选两个不同的点 i 和 j使得min(a_i b_j, a_j b_i)最大。然后把这个最大值加 1再和原最短路取 min就是最终答案。这个min(a_i b_j, a_j b_i)的形式是问题的核心难点。因为外面套了一个 min你没法直接把两个点的属性独立开来考虑。如果只是求a_i b_j的最大值那太简单了分别取 a 的最大值和 b 的最大值就行。但加了 min 之后两个项互相制约你取 a 最大的点可能 b 很小取 b 最大的点可能 a 很小必须综合考虑。这就是差值排序技巧要解决的问题。下面我先讲清楚这个技巧的一般形式再回到这道题具体怎么用。3. 差值排序技巧的通用套路从二维枚举到一维扫描3.1 一个更简单的例子引入先看一个简化版的问题帮你建立直觉。假设我给你 k 个数对(a_i, b_i)让你选两个不同的 i 和 j使得min(a_i b_j, a_j b_i)最大。不考虑图论背景纯粹看这个数学问题。假设我们固定 i 和 j并且假设a_i b_j a_j b_i那么min取的就是a_i b_j。这个不等式可以变形a_i b_j a_j b_i a_i - b_i a_j - b_j也就是说如果我们按照a_i - b_i的值对所有的点排序那么对于排在前面的点 i 和排在后面的点 j即a_i - b_i a_j - b_j一定有a_i b_j a_j b_i此时min(a_i b_j, a_j b_i) a_i b_j。这个观察太关键了。它告诉我们一旦按照a - b排序那么对于任意一对 (i, j) 且 i 排在 j 前面min 的值就确定是a_i b_j不再有歧义。这样我们就把那个讨厌的 min 消掉了。3.2 排序之后怎么扫描排序之后问题变成在排序后的序列中选两个位置 i j使得a_i b_j最大。这个问题就非常好办了。我们只需要从左到右扫描维护一个到目前为止最大的 a 值对于每个位置 j用max_a_so_far b_j更新答案然后用a_j更新max_a_so_far。为什么这样是对的因为对于固定的 j我们要找的是它前面所有点中 a 值最大的那个 i这样a_i b_j才最大。而扫描的过程中max_a_so_far正好维护了这个信息。整个算法复杂度 O(k log k)排序的复杂度扫描是 O(k)。回到原题我们算出这个最大值之后加 1再和原最短路取 min就是最终答案。因为加边之后的最短路不可能比原最短路还长加边只会让路更短或不变所以最后要取 min。3.3 为什么这个技巧叫差值排序名字来源就是排序的依据按照a_i - b_i这个差值排序。这个差值的正负和大小决定了在 min 表达式中哪一项更小。本质上差值排序是在消除 min/max 带来的对称性把一个需要同时考虑两个点、两个维度的优化问题转化为一个单向扫描问题。这个技巧的适用范围很广。只要你的目标函数是min(a_i b_j, a_j b_i)或者max(min(...), ...)这类形式并且两个点的属性可以分离成加法形式就可以考虑用差值排序。类似的还有max(a_i b_j, a_j b_i)的形式那个更简单直接取 a 最大和 b 最大配对就行不需要排序。我个人的经验是看到选两个元素目标函数里同时出现两个元素的属性并且有 min 或 max 嵌套的时候第一反应就应该是能不能排序消掉 min/max。差值排序是最常用的一种消法。4. 完整代码实现与逐行拆解4.1 预处理两次 BFS 求距离数组#include bits/stdc.h using namespace std; const int MAXN 2e5 5; vectorint adj[MAXN]; int d1[MAXN], dn[MAXN]; int special[MAXN]; int n, m, k; void bfs(int src, int dist[]) { fill(dist, dist n 1, -1); queueint q; dist[src] 0; q.push(src); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } }这段代码没什么好说的标准的 BFS 求无权图最短路。从起点 1 跑一次得到d1[]从终点 n 跑一次得到dn[]。注意图是连通的所以所有点都会被访问到不存在距离为 -1 的点。有个小细节fill(dist, dist n 1, -1)这里数组大小要开到 n1因为点的编号是 1 到 n。我见过有人开成 n 然后越界调半天调不出来。4.2 核心排序与扫描int main() { scanf(%d %d %d, n, m, k); for (int i 0; i k; i) { scanf(%d, special[i]); } for (int i 0; i m; i) { int u, v; scanf(%d %d, u, v); adj[u].push_back(v); adj[v].push_back(u); } bfs(1, d1); bfs(n, dn); int original d1[n]; // 按照 d1 - dn 排序 vectorpairint,int pts; for (int i 0; i k; i) { int u special[i]; pts.push_back({d1[u] - dn[u], u}); } sort(pts.begin(), pts.end()); int best -1e9; int max_a -1e9; for (int i 0; i k; i) { int u pts[i].second; int a d1[u], b dn[u]; if (i 0) { best max(best, max_a b); } max_a max(max_a, a); } int ans min(original, best 1); printf(%d\n, ans); return 0; }核心逻辑就这几行。pts数组存的是每个特殊点的(d1 - dn, 点的编号)按差值排序。然后从左到右扫描max_a维护当前点之前所有点的d1最大值。对于当前点用max_a dn[u]更新 best。最后best 1是经过新边的最短路和原最短路取 min。4.3 几个容易写错的边界第一个坑best的初始值。因为距离都是非负的best至少是 0但为了安全我习惯初始化为一个很小的负数。如果你初始化为 0在某些极端情况下比如 k1但题目保证 k2可能出问题。第二个坑扫描的时候必须先更新 best 再更新 max_a。因为我们要选两个不同的点当前点不能和自己配对。如果先更新 max_a 再更新 best就可能出现自己和自己配对的情况虽然在这道题里a_i b_i不一定是最优但逻辑上是错的。第三个坑最后取 min 的时候best 1可能比原最短路大也可能小。如果加的边没有改善最短路那答案就是原最短路。这个 min 不能忘。第四个坑排序的依据是d1[u] - dn[u]不是dn[u] - d1[u]。方向反了的话min 的取值就反了扫描逻辑也要跟着改。我建议统一用d1 - dn升序然后 min 取a_i b_ji 在前。5. 为什么排序能消掉 min一个几何视角的解释5.1 把每个点看成平面上的一个点每个特殊点 i 可以看成二维平面上坐标为(a_i, b_i)的一个点其中a_i d1[i]b_i dn[i]。我们要最大化的min(a_i b_j, a_j b_i)可以理解为对于两个点 i 和 j考虑两条交叉路径的长度取较短的那条。如果我们把点按照a - b排序实际上是在按照点到直线y x的投影排序。a - b越大点在直线y x的右下方越远a - b越小点在左上方越远。对于两个点 i 和 j如果 i 在 j 的左上方即a_i - b_i a_j - b_j那么从 i 出发走 a 方向、从 j 出发走 b 方向的路径a_i b_j一定比反过来的a_j b_i短。这就是为什么排序之后 min 可以确定。5.2 和最大曼哈顿距离问题的联系这个技巧和经典的求平面上最远曼哈顿距离问题有异曲同工之妙。那个问题是求max(|x_i - x_j| |y_i - y_j|)做法是拆绝对值符号分成四种情况每种情况排序后扫描。本质也是通过排序消除绝对值类似 min/max的对称性。我个人的理解是凡是目标函数里出现了取绝对值取 min取 max这种非线性操作并且操作的对象是两个元素的属性组合就应该考虑能不能通过排序把非线性操作变成线性的。差值排序是其中最常见的一种。5.3 为什么不能直接取 a 最大和 b 最大有人可能会想既然要最大化min(a_i b_j, a_j b_i)那我直接找 a 最大的点和 b 最大的点配对不就行了这个想法是错的。举个例子点 1 是 (100, 0)点 2 是 (0, 100)点 3 是 (50, 50)。a 最大的是点 1b 最大的是点 2配对得到min(100100, 00) 0。而点 1 和点 3 配对得到min(10050, 500) 50点 2 和点 3 配对得到min(050, 50100) 50。显然 50 比 0 好。这个例子的教训是min 的存在使得贪心地取极值失效必须综合考虑两个维度。差值排序正是为了解决这个综合问题。6. 实测中的坑与调试经验6.1 数组越界与初始化问题这道题的数据范围是 n, m, k 都到 2×10⁵数组要开到 2×10⁵ 5。我见过有人开2e5结果 RE因为点的编号最大是 n数组下标要能访问到 n。另外 BFS 的 dist 数组每次都要重新初始化不能复用上一次的结果。还有一个隐蔽的坑如果图中有重边或自环BFS 仍然能正确处理因为 BFS 只关心第一次访问。但如果你用邻接矩阵存图重边会导致覆盖不过这道题用邻接表没这个问题。6.2 排序键的选择与稳定性排序的时候我用的是pairint,int第一关键字是差值第二关键字是点的编号。第二关键字其实无所谓因为差值相同的点之间顺序不影响结果它们的 a 和 b 关系是等价的。但如果你用自定义比较函数要注意严格弱序不能写成否则可能 RE。我实测下来用pair默认排序最省心不用自己写比较函数也不容易出错。6.3 答案的边界情况考虑 k2 的情况只有一对特殊点直接算就行。考虑加边之后最短路反而变短的情况其实加边只会让最短路不变或变短不会变长所以最后一定要和原最短路取 min。考虑原图 1 到 n 本来就很短加边之后还是那么短答案就是原最短路。还有一个边界如果特殊点里包含起点 1 或终点 n加边的时候可能会用到它们。比如在 1 和某个特殊点之间加边那新路径就是1 dn[v]这个在我们的公式里也能正确处理因为d1[1] 0。6.4 复杂度分析与实测表现整个算法的时间复杂度是 O(n m k log k)两次 BFS 是 O(nm)排序是 O(k log k)扫描是 O(k)。对于 2×10⁵ 的数据量这个复杂度绰绰有余实测在主流评测机上跑完所有测试点不超过 200ms。空间复杂度是 O(n m k)邻接表存图 O(nm)距离数组 O(n)特殊点数组 O(k)。内存占用也很小完全不用担心 MLE。7. 差值排序的变体与举一反三7.1 max 形式的对称处理如果目标函数是max(a_i b_j, a_j b_i)处理方式类似但更简单。假设a_i - b_i a_j - b_j那么a_i b_j a_j b_imax 取a_i b_j。排序后扫描维护 max_a对于每个 j 用max_a b_j更新答案。其实和 min 的形式代码几乎一样只是排序方向和更新逻辑要对应调整。7.2 三个元素的组合优化如果问题变成选三个点目标函数是三个两两组合的 min 或 max差值排序就不够用了可能需要更复杂的技巧比如枚举中间点、或者用数据结构维护。但两个元素的组合优化差值排序基本是通杀。7.3 带权图的情况这道题的边权都是 1所以 BFS 就够了。如果边权是任意正数就要用 Dijkstra 求距离数组后面的排序扫描逻辑完全一样。差值排序本身不依赖于边权只依赖于距离数组的值。7.4 在工程问题中的类比差值排序的思想在工程中也有应用。比如你要从一批服务器里选两台做负载均衡每台服务器有读能力和写能力两个指标你要最大化两台服务器组合后的最小吞吐。这本质上就是min(a_i b_j, a_j b_i)的形式可以用差值排序快速求解而不需要枚举所有服务器对。再比如任务调度中你要把两个任务分配给两个工人每个工人做每个任务的时间不同你要最小化总完成时间的最大值。这类问题经过转化后也常常能用类似的排序技巧解决。8. 从这道题学到的通用解题思维这道题给我最大的启发不是差值排序本身而是转化问题的思维方式。原始问题是加一条边使最短路最大看起来是一个图论问题但经过分析之后图论的部分BFS 求距离只是预处理真正的核心是一个纯粹的数学优化问题。把图论问题转化为数学问题再用排序技巧解决这个转化链条非常漂亮。另一个启发是消除非线性操作的思路。min、max、绝对值这些操作在优化问题中往往是难点因为它们破坏了线性结构。但通过排序我们可以把非线性操作变成确定性的选择从而把问题线性化。这个思路在算法竞赛中反复出现值得刻意练习。最后我想说的是这道题虽然难度不算特别高CF 上大约 1900 分左右但它把图论预处理 数学转化 排序技巧三个点结合得很好是一道非常适合用来学习差值排序的题目。如果你能把这道题彻底吃透以后遇到类似的选两个元素优化组合表达式的问题基本都能找到思路。我在实际写这道题的时候第一次 WA 是因为忘了和原最短路取 min第二次 WA 是因为排序方向搞反了第三次才过。这些坑我都写在上面了希望你能一次过。