最近打卡刷到第2931题碰上了 CSP-S 2019 江西的 P5687《网格图》。老实说第一眼看到题面只有两行数组的时候我内心是开心的感觉比那些又臭又长的模拟题清爽多了真正动手之后才发现这题就是典型的“看着简单想清楚不简单”。我先把同场的 P5627 过了一遍再回头看 P5687发现自己对“最小生成树 等价类压缩”的理解深了不少。这篇文章不打算只贴代码我会把从暴力 Kruskal 到行列批处理的整个推导过程重新走一遍再把 C 实现和踩过的边界坑都写清楚希望对正在刷 CSP-S 题单的朋友有点帮助。1. 一眼看过去这题到底给我们画了什么图1.1 题目模型拆开讲给定一个 n 行 m 列的网格每个格点是一个节点相邻节点之间有一条边。特殊之处在于第 i 行所有横向边的权值都等于a[i]第 j 列所有纵向边的权值都等于b[j]。也就是说整个图虽然节点数可能到几十亿但边的权值信息只有n m个。举个例子a[1]表示第一行里(1,1)-(1,2)、(1,2)-(1,3)、一直到(1,m-1)-(1,m)这些横向边的权值b[2]表示第二列里(1,2)-(2,2)、(2,2)-(3,2)一直到(n-1,2)-(n,2)这些纵向边的权值。题目要求整张网格图的最小生成树权值和。如果你和我一样第一反应是“直接建图跑 Kruskal”那很快就会发现事情没那么简单。横向边数是n * (m - 1)纵向边数是m * (n - 1)总共大约是2nm条边。当 n 和 m 都取到上限 300000 时边数是1.8e11。这个数量级连存储都不现实更谈不上排序。哪怕每条边只存三个 int也要超过 2TB 内存。所以这道题的核心考点不是“你会不会 Kruskal”而是“你能不能发现边权是成组出现的并且利用这个结构把边压缩成批次来处理”。1.2 关键词行列对称网格图在信奥题里经常出现但大多数网格图题都是给每个格子或每条边单独权值。这题偏偏反着来同一行权值相同同一列权值相同。这就在暗示我们解法的复杂度应当只和n m有关而不是和边数nm有关。我当时就在草稿纸上画了一个 3 乘 3 的网格把行权和列权随便填了几个数然后手动用 Kruskal 跑了一遍。跑完之后发现某些横向边虽然权值很小但可能完全冗余某些纵向边则在关键位置连接两个大块。这个现象说明我们不能简单地把整行m-1条边全加入答案也不能把整列n-1条边全加入答案必须知道当前这一行或这一列上到底还有多少个“缺口”需要填补。2. 压缩思路把三百亿条边变成 nm 次操作2.1 每个行权和列权对应一个“批次”在 Kruskal 算法中所有边会按权值从小到大依次处理。由于同一行的所有横向边权值相等它们在被排序时必然是连续的一段同一列的所有纵向边也是同理。因此我们可以把“第 i 行”看成一批横向边把“第 j 列”看成一批纵向边然后按这两类批次的权值做归并。这里要注意一个关键点所谓“处理一批行”并不是把这一行的m-1条边全部加入。Kruskal 会一条一条检查如果这条边连接的两个点已经连通就跳过如果还没有连通就加入。一批行处理完之后这一行上的 m 个点最终会被连成一个连通块但实际加入的边数可能小于m-1。比如一个 3 行 3 列的图先把第 1 列和第 2 列的纵向边都处理完此时这两列各自形成一条竖链。再处理第 1 行时这一行上原本有 3 个点但第 1 列和第 2 列上的两个点其实已经可以通过绕路连通所以第 1 行的横向边只需要 2 条就能把 3 个点串成一个连通块而不是把(1,1)-(1,2)和(1,2)-(1,3)两条都当成“必须新加入”。2.2 维护两个状态已经处理过多少行、多少列既然要判断当前批次里有多少边是真正有效的我们就需要知道目前整个网格图已经连通成什么样子。进一步观察可以发现由于行与行之间地位对称、列与列之间地位对称我们根本不需要关心具体是哪些行、哪些列被处理过只需要记住两个数字rowUsed已经处理过的行数。colUsed已经处理过的列数。这两个数字足以推出当前新处理一批行或一批列时会有多少条有效边。举个直觉例子如果已经处理过很多列那么这些列都变成了“竖梯”可以帮助不同行之间上下移动如果已经处理过很多行那么这些行都变成了“横桥”可以帮助不同列之间左右移动。但只有“竖梯”和“横桥”同时存在时网状路径才会真正形成冗余边才会开始大量出现。2.3 核心递推处理一批行时新增几条边现在考虑当前要处理一批行。这一行的 m 个点在 Kruskal 处理该批次之前被分成了多少个连通块假设块数是 k那么这行横向边实际加入的数量就是k - 1。分情况讨论如果rowUsed 0说明之前没有任何已处理的行也就是没有“横桥”。就算某些列已经被处理成竖链这些竖链之间也无法横向连通所以这一行上的 m 个点只能各自独立块数 k m需要m - 1条边。如果colUsed 0说明之前没有任何已处理的列也就是没有“竖梯”。即使已经处理了很多行这些行之间也无法上下走动所以当前行的 m 个点依然无法合并块数 k m需要m - 1条边。如果rowUsed 0且colUsed 0此时横桥和竖梯都齐了。任取一个已处理列 p 和一个已处理列 q点(当前行, p)可以先沿 p 列的竖边走到某个已处理行再沿该行的横边走到 q 列最后沿 q 列的竖边回到当前行。这说明所有已经处理过的列在当前行上已经属于同一个连通块。于是这一行的 m 个点中有colUsed个点会被合并成 1 个大块剩下m - colUsed个未处理列对应的点各自独立。总块数为k (m - colUsed) 1所以有效边数就是k - 1 m - colUsed如果colUsed m说明这一行上所有点早就连通了横向边一条都不用加这个公式也会给出 0。处理一批列的逻辑完全对称。当前要处理一批列该列的 n 个点之前如果既存在已处理行、又存在已处理列那么所有已处理行上的点会合并成一个大块有效边数为n - rowUsed否则就是n - 1。3. 新增边数的计算公式是怎么推出来的3.1 用路径连通性说话这部分是我认为全题最关键的地方值得写进题解。很多人第一次看公式会用“记忆”的方式接受它但换个边界条件又糊涂了。所以我特意把推导过程单独拎出来。为什么rowUsed 0或colUsed 0时新增边数取的是满值m-1因为 Kruskal 的本质是并查集合并。同一行的两个点如果它们已经在同一个连通块里这条横向边就冗余要判断它们是否连通必须存在一条由已处理边构成的路径。而一条横向路径需要在某个时刻通过纵向边“上车”到另一行去绕。如果根本没有已处理的行绕路的“地面层”不存在如果根本没有已处理的列绕路的“电梯”不存在。二者缺一那么当前行的 m 个点之间没有任何跨列路径每一列点都是一个独立连通块。反过来说当二者都存在时任意两个已处理列之间的路径是当前行 - 上/下到某个已处理行 - 横向走到目标列 - 再垂直回到当前行。这条路径经过了已处理的行边和已处理的列边完全合法。因此所有已处理列在当前行上“等价”于一个点。这个“等价类压缩”的想法正是整道题的解药。3.2 为什么排序后的贪心是对的普通 Kruskal 对所有边排序是按边权从小到大一条条处理。我们把它压缩成批次后每个批次内部边的权值都相同。Kruskal 处理一批相同权值的边时边的内部顺序无关紧要结果只看这批边之前已经形成了多少连通块。两个序列分别排好序后处理顺序就是每次比较当前最小行权和最小列权取较小的那一侧作为下一批。这等价于把所有行批次和所有列批次按权值归并成一个全局顺序。剩下的问题就是按照这个顺序处理时每一批实际加入多少条边只和之前的rowUsed、colUsed有关而和具体是哪一行、哪一列无关。这保证了贪心的正确性。有个细节要说明我们并不需要真的去并查集维护那些数量巨大的节点。因为节点数是n*m直接开并查集会爆。上面的公式已经帮我们算出了“这一批会产生多少次并查集合并”因此只需要维护行和列的计数即可。4. C 代码实现和最容易翻车的三个细节4.1 完整可 AC 的代码下面是这题的标准 C 实现。代码量不大但几个细节值得反复看。#include bits/stdc.h using namespace std; const int N 300000 5; long long a[N], b[N]; int main() { int n, m; scanf(%d%d, n, m); for (int i 1; i n; i) scanf(%lld, a[i]); for (int i 1; i m; i) scanf(%lld, b[i]); // 只有一行或只有一列时另一方向没有边直接特判 if (n 1 || m 1) { long long ans; if (n 1) ans a[1] * 1LL * (m - 1); else ans b[1] * 1LL * (n - 1); printf(%lld\n, ans); return 0; } sort(a 1, a n 1); sort(b 1, b m 1); int i 1, j 1; int rowUsed 0, colUsed 0; long long ans 0; while (i n || j m) { // 当前行权值更小或者列已经处理完 if (j m || (i n a[i] b[j])) { long long add; if (rowUsed 0 || colUsed 0) { add m - 1; } else { add m - colUsed; } ans a[i] * add; rowUsed; i; } else { long long add; if (rowUsed 0 || colUsed 0) { add n - 1; } else { add n - rowUsed; } ans b[j] * add; colUsed; j; } } printf(%lld\n, ans); return 0; }4.2 细节一必须用 long long答案的最大值可能超过 int。网格图有n*m个节点最小生成树的边数是n*m - 1每条边权值最大可能到 1e9。就算 n、m 都只有 3e5n*m也是 9e10答案理论上可以达到 9e19虽然实际数据不一定这么极端但用long long是必需的。输入输出我用的是scanf/printfcin/cout加上关闭同步也够用。如果你喜欢快读自己封装一个也行。4.3 细节二相等权值用不会错代码里选了a[i] b[j]时优先处理行。有些题解用让列优先。实测下来二者答案一样。原因还是 Kruskal 的性质同一个权值级别内先处理哪一批都不会改变最终总权值因为 Kruskal 只要保证每次加入的是当前最小边最终生成树就是最优的。不过要注意虽然最终答案一样但中途的rowUsed和colUsed会不同因此add也可能不同。别去手动模拟一个“全相等权值”的用例后觉得代码算错了只要最后总权值对就没问题。4.4 细节三为什么必须特判 n1 或 m1我之前第一次交就是栽在这里。当n 1时整个图其实只有一条横向链答案是a[1] * (m-1)和b数组完全无关。但如果走通用循环程序会先去处理权值可能比行权小的列批次把colUsed加到 m等再回头处理行时add m - colUsed 0答案就变成 0 了。这是因为当 n 1 时每一列纵向边的数量是 0这些列批次根本不应该被处理。同理m 1时行批次也不该处理。特判虽然看起来“暴力”但最稳妥。5. 边界数据验证与同场题目复盘5.1 三组手算验证为了让自己相信公式没问题我在本地跑了几组手算样例也推荐大家用同样的方式验证代码。样例一2 2 1 100 50 100手动 Kruskal先取第一行横向边权值 1边数 1再取第一列纵向边权值 50边数 1最后从第二行横向边和第二列纵向边里随便选一条权值 100。总权值 151。代码走一遍排序后a[1,100]b[50,100]。优先选行 a[1]rowUsed0,colUsed0加1*(2-1)1接着选列 b[1]colUsed0加50*(2-1)50最后 a[2] 和 b[2] 都是 100按先选行此时rowUsed1,colUsed1addm-colUsed1加 100。总数 151正确。样例二3 3 1 1 1 1 1 1全相等的最小生成树权值就是边数n*m-1 8。用代码跑先选行 1加2再选行 2加2选行 3加2然后列 1 权值 1此时rowUsed3,colUsed0选列走另一个分支加n-12。总权值22228正确。虽然之后程序还会继续处理列但add变成 0不影响答案。样例三3 3 2 100 100 5 100 100让行权 2、列权 5 先各自发挥作用后面 100 再补边。手动计算中最少生成树的权值是 414。代码最终也会得到 414。这类不等权样例能有效抓住公式中间变量是否写反。5.2 同场 P5627 的联动思考CSP-S 2019 江西这套题里P5627 和 P5687 放到一起刷很有感觉。两道题都不是让你背一个裸模板而是先给你一个“看起来规模爆炸”的模型再逼你找到压缩信息的方式。P5687 的压缩对象是“同权值的成组边”核心操作只是排序加计数P5627 的思路也类似需要从构造中提取关键参数而不是盲目展开。如果你和我一样卡在 P5687建议回过头去把 P5627 的构造过程重新写一遍很多“为什么这个题能这么做”的疑问会在对比中消失。5.3 本地对拍小技巧最后分享一个刷题时的土办法当 n、m 都很小比如小于等于 6 时可以直接暴力建图跑 Kruskal然后把结果和这个优化算法对比。我写了一个n,m5的暴力对拍随机生成行列权值跑了上万组两边答案完全一致。这个对拍脚本比任何证明都能让你踏实。具体写法就是把网格图的点映射成i*mj存放所有边跑经典 Kruskal计算权值。然后把同样的行列权值丢进上面的代码比较两个答案。如果某组数据不一致大概率是公式里的rowUsed和colUsed写反了或者特判没写好。说句实在话P5687 这道题的思维量并不低但代码一旦想明白就非常好写。希望这篇复盘能帮你少走一点弯路。如果你也在刷这套题拿这题练“找等价类”的眼光会比单纯记一个结论收获更多。