第一次在洛谷看到 P3073 [USACO13FEB] Tractor S我脑子里冒出来的第一反应是“这不就是一个二维连通性问题吗” 但真的拿起键盘写的时候才发现题目问的根本不是“能不能走通”而是“要让拖拉机把所有格子都走遍最大允许的高度差最少是多少”。这一字之差才是整道题的灵魂。这篇文章不是简单的题解复述我把自己从审题到 AC、再到试了三种不同做法的过程完整拆开希望能帮你把这道题吃透。这道题很典型它明明是一道网格图题但真正考的却是二分答案、最小瓶颈生成树、以及“把最短路思想迁移到最大边权”这三个看似不相关的知识点。无论你是刚学 C 想找题目练手还是准备 USACO 这种带分类的算法竞赛P3073 都非常值得花一个晚上好好研究。1. 先想清楚这题到底在求一个什么值1.1 四个方向移动背后的“边权”题目给了一个 n 行 m 列的田野每个格子上有一个高度值。拖拉机有四个方向可以走上下左右。限制只有一个如果两个相邻格子的海拔差绝对值超过某个数 D拖拉机就过不去。这个描述如果只是口头理解很容易被带偏。很多人会想那我假设 D 很大所有格子都能走BFS 一遍统计一下从起点能到多少个格子完事了。可是题目问的不是“给你一个固定的 D判断能不能走完”而是“要让所有格子都能走完D 最小是多少”。所以这个 D 才是真正的答案而 D 本身又是一个“阈值”。这题的关键就是你既要判断某个具体阈值行不行又要找到最小的那个阈值。把问题抽象成图之后会清楚很多。把每个格子看成一个点相邻格子之间连一条无向边边的权值就是这两个格子的高度差绝对值w((i,j), (i1,j)) |h[i][j] - h[i1][j]| w((i,j), (i,j1)) |h[i][j] - h[i][j1]|如果我把所有边权都列出来那“阈值 D 可行”的意思就是只能走边权 ≤ D 的边从起点出发能否到达所有点。这本质上是在问在只保留一部分边的前提下起点所在连通块是否等于整个点集。这个转换非常重要。因为一旦有了边权整道题就可以从“二维地图题”变成“图论题”后面所有算法都是建立在这个模型上的。1.2 为什么答案会落在一棵树上继续想一步。如果 D 可行那么所有边权 ≤ D 的边组合在一起一定能让起点连通到所有格子。注意我说的不是“路径”而是整个子图里起点所在的连通块覆盖了全部格子。在这个子图里必然会存在一棵生成树它包含所有点并且每条边的权值 ≤ D。也就是说只要存在一个生成树使得树上从起点到任意点的最大边权 ≤ DD 就可行。反过来也一样。如果存在一棵这样的树那走这棵树上的边就已经足够连通所有点了不需要额外的边。所以问题可以等价改写成在所有覆盖全部格子的生成树中找到一棵树使起点到所有点路径上的最大边权最小值最大不对是“最大边权尽量小”。这就是经典的“最小瓶颈生成树”Minimum Bottleneck Spanning Tree问题。从起点出发去看答案就是“最小生成树上起点到所有点路径的最大边权”。可能有同学会问为什么一定是最小生成树而不是别的树因为别的树的最大边权可能更大而最小生成树保证了“连接所有点所需的边权上界最小”。这个性质可以通过 Kruskal 算法的执行过程看出来后面第三章会详细证明。1.3 答案的上下界在写算法之前先把答案的取值范围定下来。高度值肯定有范围假设所有格子里最小高度是 L最大高度是 R。两个格子高度差再大也不会超过 R - L。所以当 D R - L 时任意相邻格子的高度差都 ≤ D整张图必然是连通的答案一定不会超过 R - L。下界就是 0。如果所有格子高度都一样拖拉机什么都不用怕D 0 直接能走完。如果不想用 R - L 作上界更紧一点可以扫描所有相邻边取 max(w)。这样二分次数会少一点点实际差别不大但在边界情况下更严谨。我一开始图省事直接用了 maxH - minH也能 AC但后面被一道类似的题目坑过所以还是建议你扫描一遍边权取最大值作上界。2. 二分 BFS最没有理解成本的做法2.1 check 到底在查什么二分答案的思路非常符合直觉因为答案是单调的。如果 D 可行那么任何比 D 大的数也可行。既然单调就能二分。二分里面核心是 check(D)从起点开始 BFS只走高度差绝对值 ≤ D 的边统计能到达多少个格子。如果统计结果是 n * m说明 D 可行否则不可行。这个 check 的写法比你想的还要直接一个 vis 数组防止重复访问。一个队列存当前可以到达的格子坐标。一个 cnt 变量记录访问过的格子数量。对每个弹出的格子检查上下左右四个方向只要在边界内、没访问过、高度差满足条件就入队并 cnt。有一个小优化当 cnt 已经等于 n * m 时可以直接返回 true不用把剩余队列跑完。这在数据大的时候能省不少时间。很多新手会有一个疑问为什么这里用 BFS 而不用 DFSDFS 递归写起来更短但是在 n * m 很大的情况下比如 500×500 甚至 1000×1000递归深度可能非常大会有爆栈风险。BFS 用队列实现不存在这个问题。在竞赛中用 BFS 也更稳。2.2 完整代码#include bits/stdc.h using namespace std; const int N 505; int n, m, sx, sy; int h[N][N]; bool vis[N][N]; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; bool check(int d) { memset(vis, 0, sizeof(vis)); queuepairint, int q; q.push({sx, sy}); vis[sx][sy] true; int cnt 1; while (!q.empty()) { auto [x, y] q.front(); q.pop(); if (cnt n * m) return true; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 1 || nx n || ny 1 || ny m) continue; if (vis[nx][ny]) continue; if (abs(h[nx][ny] - h[x][y]) d) continue; vis[nx][ny] true; q.push({nx, ny}); cnt; } } return cnt n * m; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m sx sy; int minH 1e9, maxH -1e9; for (int i 1; i n; i) { for (int j 1; j m; j) { cin h[i][j]; minH min(minH, h[i][j]); maxH max(maxH, h[i][j]); } } int l 0, r maxH - minH; int ans r; while (l r) { int mid (l r) / 2; if (check(mid)) { ans mid; r mid - 1; } else { l mid 1; } } cout ans \n; return 0; }我自己本地测试时造过这样一组数据3 3 1 1 1 3 5 2 4 6 5 7 9所有相邻格子的高度差不是 1 就是 2。D 1 的时候从 (1,1) 能走到 (2,1)再从 (2,1) 能走到 (3,1)但到不了右边三列因为水平方向高度差是 2。D 2 的时候整张图连通输出就是 2。这个样例跑一遍基本能验证代码写没写错。2.3 复杂度与边界二分次数是 log2(R - L 1)。如果 R - L 是 10^9大概 31 次。每次 check 的 BFS 是 O(n * m)。所以总复杂度是 O(n * m * log(R - L))。在 n、m 都是 500 的情况下n*m 25000030 次 BFS 也就 750 万次操作C 一秒内毫无压力。就算 n、m 是 1000也才 3000 万次依然可行。这里有个细节check 里 memset(vis, 0, sizeof(vis)) 每次都会把整个二维数组刷一遍。如果 n、m 是 1000一次 memset 是 100 万个 int30 次就是 3000 万问题不大。但如果你把 N 开到 2000n*m 达到 400 万那 memset 开销就会明显上升。更稳妥的做法是用 int stamp[N][N] 配合时间戳每次 check 不需要清空整个数组。不过这题用不上知道有这种技巧就行。二分的时候还有一个容易错的点当 check(mid) 为 true说明当前 mid 可行我们要记录 ans mid然后向更小的方向找所以 r mid - 1。很多人第一次写的时候会写成 l mid 1 然后 ans 永远错过最小值。我是吃了这个亏才把 ans 单独保存的。3. Kruskal 加边法通过并查集直接定位答案3.1 最小瓶颈生成树的直观证明二分BFS 很简单但还有更优雅的做法。把所有相邻边收集起来按边权从小到大排序。然后用并查集逐渐加边维护每个连通块的大小。一旦起点所在的连通块大小等于 n * m当前刚加入的这条边的权值就是答案。为什么因为 Kruskal 是在从小到大处理边。处理完所有边权 ≤ D 的边之后并查集里的连通关系和“只保留边权 ≤ D 的边”这个子图的连通关系是完全一致的等权边顺序不影响最终连通性。假设答案不是当前这条边 w而是一个更小的值 k。那么处理完所有边权 ≤ k 的边之后起点就连通了所有格子。可我们在处理边权 k 对应边的时候当时起点连通块并没有覆盖全部点否则早就输出了。这就矛盾了。所以Kruskal 加到“起点所在连通块第一次覆盖全部格子”时当前边权一定是最小可行阈值。有人可能会问这不就是最小生成树吗其实我们不需要真的生成完整最小生成树也不需要关心总权值最小。我们只是借助 Kruskal 从小到大加边这个单调过程找到那个“临界边权”。这也是为什么叫最小瓶颈生成树树上瓶颈的最小值等于所有生成树中最大边权的最小值。3.2 相邻边生成与代码骨架网格图生成边有个技巧只需要往右和往下两个方向看就能收集到所有无向边避免重复。for (int i 1; i n; i) { for (int j 1; j m; j) { int u id(i, j); if (i n) edges.push_back({u, id(i1, j), abs(h[i][j] - h[i1][j])}); if (j m) edges.push_back({u, id(i, j1), abs(h[i][j] - h[i][j1])}); } }节点编号直接二维转一维int id(int i, int j) { return (i - 1) * m j; }并查集只维护两个东西fa 数组和 sz 数组。sz[rt] 表示根为 rt 的连通块大小。合并时把小的并到大树上可以优化但这题数据量不大不按秩合并问题也不大。核心是在每次成功合并后检查int rt find(id(sx, sy)); if (sz[rt] n * m) { cout e.w \n; return 0; }注意一定是find(id(sx, sy))先找到真正的根再去访问 sz[rt]。我第一次写的时候直接判断sz[id(sx, sy)] n*m结果当然不对因为起点可能不是根sz 只维护根的个数。Kruskal 版本完整代码关键部分#include bits/stdc.h using namespace std; const int N 505; struct Edge { int u, v, w; }; int n, m, sx, sy; int h[N][N]; int fa[N * N], sz[N * N]; vectorEdge edges; int id(int i, int j) { return (i - 1) * m j; } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m sx sy; for (int i 1; i n; i) { for (int j 1; j m; j) { cin h[i][j]; } } int total n * m; for (int i 1; i total; i) { fa[i] i; sz[i] 1; } for (int i 1; i n; i) { for (int j 1; j m; j) { int u id(i, j); if (i n) edges.push_back({u, id(i1, j), abs(h[i][j] - h[i1][j])}); if (j m) edges.push_back({u, id(i, j1), abs(h[i][j] - h[i][j1])}); } } sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { return a.w b.w; }); int target id(sx, sy); for (const Edge e : edges) { int fu find(e.u); int fv find(e.v); if (fu fv) continue; fa[fu] fv; sz[fv] sz[fu]; int rt find(target); if (sz[rt] total) { cout e.w \n; return 0; } } return 0; }这段代码如果全图一开始就不连通理论上应该不会发生因为题目保证存在答案。而且当 D 足够大时所有边都能走起点总能连通所有点。3.3 第一次 AC 时的注意点Kruskal 版本最直观的坑就是我上面说的find(target)后取 sz。还有一个坑是排序边之后如果fu fv直接跳过但这不影响 sz 判断因为连通块没变化不可能突然满足条件。另外如果题目给出的 n、m 可能达到 1000总节点数是 10^6fa 数组、sz 数组要开 1000005Edge 数量接近 2 * 10^6。vector 动态扩容会浪费时间最好在 push 前reserve(2 * n * m)或者用静态数组。虽然 P3073 的数据范围一般不会卡这么死但这是个好习惯。Kruskal 版本的复杂度主要取决于排序O(E log E)其中 E 大约是 2 * n * m。如果是 500×500 的网格E 约 50 万排序很快。如果 n*m 到 10^6E 约 200 万排序一次也能接受但会比二分BFS 稍微慢一些。4. 优先队列扫描Dijkstra 变体一次走完4.1 dist 从“距离”变成“最大坑”第三种做法是我自己比较喜欢的一种因为它把整道题变成了一个“带边权的最短路问题”但这里的“距离”定义要换一下。设dist[i][j]表示从起点到 (i,j) 的所有路径中路径上最大边权的最小值。是不是读起来很绕举个例子。从起点到目标点有三条路第一条中间最大高度差是 10第二条中间最大高度差是 7第三条中间最大高度差是 8那么dist就是 7。因为走第二条路时你只需要忍受 7 的最大高度差就能到达目标点。如果所有格子的 dist 都算出来了答案就是所有 dist 中的最大值。因为你要“到所有格子”最后一步要到达的那个格子其 dist 就决定了全局需要的最大高度差。这个转移和 Dijkstra 几乎一模一样nd max(dist[x][y], abs(h[nx][ny] - h[x][y]))从 (x,y) 走到邻居 (nx,ny)新的“最大高度差”等于当前已经积累的最大高度差和这条新边权之间取更大的那个。然后用优先队列取出当前最小 nd 的节点继续扩展。4.2 转移式 max 的直观理解为什么不是 dist[x][y] w而是 max(dist[x][y], w)因为题目要求的不是“走过的总高度差”而是“一路上出现的最大高度差”。这是两个完全不同的概念。很多同学第一次接触这种题会条件反射地写成加法然后样例能过但大数据 WA就是没理解清楚。想象一下你骑着一辆自行车去爬山。普通最短路算的是“总爬升高度”而这个题算的是“你遇到的最陡的那个坡有多陡”。总爬升高不代表最陡的坡一定大可能有很多小坡但只要有某一个坡特别陡哪怕只出现一次你也过不去。所以状态转移是max而不是。这也是这道题和普通最短路最大的区别。优先队列代码#include bits/stdc.h using namespace std; const int N 505; const int INF 2e9; struct Node { int d, x, y; bool operator(const Node other) const { return d other.d; // 让 priority_queue 变成小顶堆 } }; int n, m, sx, sy; int h[N][N]; int dist[N][N]; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m sx sy; for (int i 1; i n; i) { for (int j 1; j m; j) { cin h[i][j]; dist[i][j] INF; } } priority_queueNode pq; dist[sx][sy] 0; pq.push({0, sx, sy}); int ans 0; int cnt 0; while (!pq.empty()) { Node cur pq.top(); pq.pop(); if (cur.d ! dist[cur.x][cur.y]) continue; ans cur.d; cnt; if (cnt n * m) break; for (int k 0; k 4; k) { int nx cur.x dx[k]; int ny cur.y dy[k]; if (nx 1 || nx n || ny 1 || ny m) continue; int nd max(cur.d, abs(h[nx][ny] - h[cur.x][cur.y])); if (nd dist[nx][ny]) { dist[nx][ny] nd; pq.push({nd, nx, ny}); } } } cout ans \n; return 0; }为什么要写if (cur.d ! dist[cur.x][cur.y]) continue;因为同一个点可能被多次入队但只有 dist 值最小的那次出队才有效。这个和普通 Dijkstra 的 lazy deletion 一样。为什么答案可以取“最后一个弹出的点的 d”因为优先队列按照 d 从小到大弹出弹出的 d 是单调不降的。当 cnt 到达总数时最后弹出的那个 d 就是全局最大值也就是答案。不需要额外再扫一遍 dist 数组。4.3 什么时候选这个思路优先队列写法的复杂度是 O(n * m * log(n * m))和 Kruskal 排序的复杂度差不多但好处是不需要提前把所有边生成出来只需要在扩展时临时算边权。不需要一个单独的“二分 check”代码更短。思想上和普通最短路很接近如果你本来就会 Dijkstra学这个版本几乎零成本。当你以后再遇到“最小化路径上最大值”这类题比如“从 A 到 B 的路径上最大边权最小”就可以直接用这个模板。它其实是二分答案的另一种优化用优先队列一次搜索代替多次 check。5. 两段可提交的代码怎么选如果你刚开始学这题我建议你从二分BFS 入手因为它最贴近题意也最容易调试。只要 check 函数写对了剩下的二分框架几乎不会出问题。如果你已经对二分答案比较熟想锻炼一下图论建模能力那 Kruskal 版本值得认真写一遍。它让你真正理解“最小瓶颈生成树”这个概念的来源。我第一次看到这个做法时有一种“啊原来答案藏在边排序后的某个位置”的震撼感。优先队列版本则适合用来记忆一类题的通用解法。它既不像二分那样需要多次 BFS又不像并查集那样需要一次性把所有边都存下来。在空间紧张的时候优先队列版本更省内存。三者的本质其实是同一个东西都依赖“阈值越小可达性越弱”这个单调性。只是表达方式不同。做法核心思想复杂度适合场景二分 BFS二分答案 可达性判断O(nm logA)思路直白适合新手Kruskal 加边最小瓶颈生成树O(nm log(nm))对并查集和生成树熟悉的人优先队列最大边权最小化O(nm log(nm))类最短路模型通用性强如果你担心代码写错建议把三份代码都自己敲一遍再用同样的随机数据对拍。这一套下来你对“网格图 边权 连通性”这类题型的理解会比其他同学高出不少。6. 我踩过的坑和实用建议6.1 起点坐标读入后没减一题目里给的起点是“第 x 行第 y 列”这是 1-based 的。如果你的二维数组也从 1 开始存那读入后直接当下标用没问题。但如果你习惯了 0-based 写法读入后一定要sx--, sy--否则起点会偏到旁边那个格子上样例也许能过但随机数据很容易挂。我自己的习惯是这道题直接用 1-based因为 USACO 这类题给的坐标描述通常都是 1-based这样最不容易错。6.2 priority_queue 的排序方向优先队列默认是最大堆也就是堆顶是最大值。如果你写struct Node { int d, x, y; bool operator(const Node other) const { return d other.d; } };那么每次弹出的都是 d 最大的节点整个搜索立刻变成错误行为。正确写法是反转比较bool operator(const Node other) const { return d other.d; }或者用现成的 pair更容易避免这种操作priority_queuepairint, pairint,int, vectorpairint, pairint,int, greater... pq;我第一版代码就是栽在这里样例数据小最后结果恰好一样换了一组大数据才发现完全不对。所以写完优先队列先打印一下弹出的顺序验证是不是非递减的。6.3 提前退出的时机二分BFS 的 check 里如果 cnt 已经等于 n*m可以直接返回 true。优先队列版本里如果 cnt 已经等于 n*m这时弹出的 cur.d 是答案可以直接 break。注意不能把答案更新放在“更新邻居”的循环里因为那个 nd 只是尝试性更新并不代表邻居的最终 dist。万一之后有一条更优路径那个 nd 会被覆盖但如果你已经记录了它作为答案就错了。安全写法是在 pop 的时候才记录答案。ans cur.d; cnt; if (cnt n * m) break;这样保证 ans 永远是“已经确定的最小 dist 值”不会出现被后面更新的情况。6.4 高度差上界别拍脑袋我一开始想当然地设r 1e9也没有问题。但更严谨的做法是扫描所有相邻边取最大差值作为上界。这样可以减少二分次数也避免某些题目里高度可能是 long long 范围时溢出。如果你用maxH - minH作为上界也基本够用但是有一个反直觉的边界当n*m 1时没有相邻边答案应该是 0。此时maxH - minH 0二分也能正确输出 0。所以这个边界其实是安全的。6.5 并查集里查连通块大小的写法Kruskal 版本里最容易写错的是 union 之后判断起点连通块大小。合并后要先find(target)找到根再访问sz[rt]。很多人在这个位置用了旧的父节点导致判断错误。而且要注意合并时我是fa[fu] fv; sz[fv] sz[fu]所以将来 sz 只在 fv 这个根上有效。如果你写成fa[fv] fu; sz[fu] sz[fv]那判断目标的根也要相应变化。总之核心是永远通过find(target)找根然后用根去取 sz。还有一个小技巧在 edge 数量特别大的时候可以先按边权排序然后一条条加。当起点所在连通块已经覆盖全图时不需要把后面的边全部处理完直接输出并 return。这样在数据大时能节省不少时间。我自己在做这道题时第一次 AC 用的是二分BFS但后来把 Kruskal 和优先队列版本都写了并且造了几组随机数据去对拍。对拍下来三个版本结果完全一致我才敢说这道题真的理解了。如果你现在卡在某个版本上我建议你不要急着看题解。先打开编辑器把自己想写的版本写出来用几组简单数据手动模拟一遍比如 1×1、2×2、所有高度相同、高度呈阶梯状变化。这些边界数据一旦跑通心里就会踏实很多。