企业官网建设流程全解析

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(n+m)。总复杂度 O(k²(n+m))，k 和 n 都是 2×10⁵ 级别，这个复杂度是天文数字，连样例都跑不过去。

稍微优化一点：其实不需要每次重新跑 BFS。我们可以先预处理出从起点 1 到所有点的最短距离d1[]，以及从终点 n 到所有点的最短距离dn[]。这两个数组各跑一次 BFS 就能得到，复杂度 O(n+m)。有了这两个数组之后，对于任意一对特殊点 (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; vector<int> 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); queue<int> 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)这里数组大小要开到 n+1，因为点的编号是 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 排序 vector<pair<int,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，在某些极端情况下（比如 k=1，但题目保证 k>=2）可能出问题。

第二个坑：扫描的时候，必须先更新 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_j（i 在前）。

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 最大的是点 1，b 最大的是点 2，配对得到min(100+100, 0+0) = 0。而点 1 和点 3 配对得到min(100+50, 50+0) = 50，点 2 和点 3 配对得到min(0+50, 50+100) = 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 排序键的选择与稳定性

排序的时候，我用的是pair<int,int>，第一关键字是差值，第二关键字是点的编号。第二关键字其实无所谓，因为差值相同的点之间顺序不影响结果（它们的 a 和 b 关系是等价的）。但如果你用自定义比较函数，要注意严格弱序，不能写成<=，否则可能 RE。

我实测下来，用pair默认排序最省心，不用自己写比较函数，也不容易出错。

6.3 答案的边界情况

考虑 k=2 的情况，只有一对特殊点，直接算就行。考虑加边之后最短路反而变短的情况（其实加边只会让最短路不变或变短，不会变长），所以最后一定要和原最短路取 min。考虑原图 1 到 n 本来就很短，加边之后还是那么短，答案就是原最短路。

还有一个边界：如果特殊点里包含起点 1 或终点 n，加边的时候可能会用到它们。比如在 1 和某个特殊点之间加边，那新路径就是1 + dn[v]，这个在我们的公式里也能正确处理，因为d1[1] = 0。

6.4 复杂度分析与实测表现

整个算法的时间复杂度是 O(n + m + k log k)，两次 BFS 是 O(n+m)，排序是 O(k log k)，扫描是 O(k)。对于 2×10⁵ 的数据量，这个复杂度绰绰有余，实测在主流评测机上跑完所有测试点不超过 200ms。

空间复杂度是 O(n + m + k)，邻接表存图 O(n+m)，距离数组 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_i，max 取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 是因为排序方向搞反了，第三次才过。这些坑我都写在上面了，希望你能一次过。