看到 CF436C 的标题 Dungeons and Candies我第一反应是这又是一道打着地牢旗号的字符串题。读完题才发现它把字符串、汉明距离和最小生成树焊死在一个完全图里思路一旦打通代码半小时内能写完建模想歪的话WA 到怀疑人生。这篇文章把这题的完整拆解记录下来从题面翻译、图论建模、算法选型到完整代码、复杂度实测和 WA 坑位一次说清楚。这道题适合三种人看刚刷到 CF 436C 准备补题的选手、想理解“为什么这题是 MST”的初学者、以及想从这题里提炼出“对象差异类包装题”通用破题套路的老手。题目本身不算难但它在 Codeforces 里很有代表性——用一层字符串外衣把最小生成树裹得严严实实看穿了就是模板题看不穿就会往 DP 或者字符串哈希上死磕。1. 题面不是字符串题先把地牢变成完全图的顶点1.1 输入输出里真正有用的变量原题的输入格式很直接第一行是n m k w之后跟着 n 行字符串。n 是地牢数量m 是每个地牢密码串的长度k 是字符集大小告诉你只会用到前 k 个小写字母w 是地牢间连边时每个差异字符要乘的代价系数。这里有个干扰项k 在整个算法过程中几乎不会用到。它只是约束了输入字符串的合法字符范围真正参与运算的只有 n、m、w。我第一次做这题时盯着 k 琢磨了好久怀疑是不是要按字符做状态压缩结果证明想多了。题目出这么个变量更像是在吓唬人让你误以为字符串性质很重要。输出则是两半第一行输出最小总代价后面 n 行按地牢编号 1 到 n 依次输出每个地牢连接的对象。如果某个地牢直接连入口就输出 0如果连到了另一个地牢 j就输出 j。1.2 把入口当成一个全是 a 的特殊字符串题面里地牢之间有两种连法第一种是直接连入口花费是当前地牢密码串中字符不是 a 的数量第二种是连到另一个地牢花费是两个字符串对应位置不同字符的数量乘以 w。这两种连法看起来是两套规则其实可以完全统一把入口看成一个额外节点 0这个节点对应的密码串就是aaaa...a长度也是 m。这样一来地牢直接连入口的代价就变成了“节点 0 与地牢 i 的汉明距离”地牢之间连边的代价则是“汉明距离乘以 w”。用汉明距离这个视角看整张图的边权结构就清晰了0 号点到普通点的边权不加权普通点和普通点之间的边权要乘 w。两条规则本质上是同一个东西只是系数不同。这个统一是建模的第一步后面写代码会省掉很多特判。1.3 自造样例什么情况下地牢间连边比直接连入口更优我拿一个自造的小样例走一遍流程方便后面解释 Prim 的选择过程。假设 n3m4w1三个密码串分别是1: bbbb 2: bbbc 3: bbcc入口 0 对应的串是aaaa。先算所有点到入口的代价地牢 1bbbb和aaaa四个位置全不同代价 4地牢 2bbbc和aaaa四个位置全不同代价 4地牢 3bbcc和aaaa四个位置全不同代价 4再算地牢之间的汉明距离1 和 2只有第 4 位不同b 对比 c差距 1乘 w 后代价 11 和 3第 3、4 位不同差距 2代价 22 和 3第 3、4 位不同再仔细看bbbc和bbcc前两位都是 bb第 3 位 b 对 c 不同第 4 位 c 对 c 相同所以差距是 1代价 1注意 2 和 3 的差距我一开始差点算错写代码时这种手算错误也会变成调试噩梦。正确答案是差距 1。这个样例里所有地牢直接连入口的总代价是 12但如果让 1 连入口代价 4、2 连 1代价 1、3 连 2代价 1总代价只有 6。这正好说明为什么不能无脑全连入口必须用 MST 去找全局最优。2. 为什么内核是最小生成树目标函数与连通性约束2.1 从管道铺设到 MST 的翻译题目要求的是从入口出发通过管道把所有地牢连成一个连通网络让总造价最小。这里的约束是“每个地牢都必须能从入口到达”也就是整张图必须连通。只要看到“n 个点 任意两点可连边 求连通全部点的最小总代价”就要立刻想到最小生成树。MST 解决的就是这个问题在一张带权无向图里找一棵边权和最小的生成树使得所有点连通。为什么不是最短路径树最短路径树关心的是从入口到每个点分别最短但它不保证整体边权和最小。举个直观例子两个地牢离入口都很远但彼此离得很近最短路径树会让它们各自拉一条长管道到入口MST 则会意识到可以让其中一个连入口另一个连在它后面省下一根长管道。这个场景和本题的糖果地牢设置完全吻合。为什么不是单纯的并查集贪心并查集贪心只在按边权从小到大合并时有效那其实就是 Kruskal 的思路没问题但很多人会忘了先对边排序或者在完全图里对边排序本身就成了瓶颈。这些我在下一章展开先把 MST 的大方向钉死。2.2 必须包含入口节点漏了这一层等于模型错误这个坑特别隐蔽。如果题目只说“让所有地牢连通”你可能会直接对 n 个地牢跑一遍 MST完全不带入口节点。这在很多连通题里是对的但在这题里是错的。题目里的入口不是一个可选的装饰性节点。每个地牢的密码串是解锁用的不连到入口人就进不去而且入口节点 0 的存在直接影响边权——地牢之间连边要乘 w而连入口不乘 w。也就是说0 号点的加入改变了整个最优解的形状。建模时必须把入口当成一个真正的图节点参与 MST 计算。等价地你可以把 0 号节点视为一个密码串为全 a 的地牢然后对所有 n1 个点跑 MST。我见过不少人在这里翻车对 n 个地牢跑出一个小得离谱的答案样例根本对不上debug 半天才发现是把自己脑子里的贪心当成了题意。2.3 这里的 MST 与普通 MST 的唯一区别完全图边权按需生成普通 MST 题通常会直接给你边集大多数用 Kruskal 就能解决。这道题的特殊之处在于它是一张完全图——n 个地牢加上入口两两之间都有边边数大约是 n(n1)/2。完全图本身不可怕关键是边权的计算方式是“实时生成”的每两个节点之间的边权要扫描一遍长度为 m 的密码串才能算出来。理论上你可以先把所有边权算出来存成邻接表再去跑 MST但当 n 到 1000、m 也到 1000 时预计算所有边权的时间和内存都不划算。更好的做法是让 MST 算法自己按需取边权。恰好 Prim 算法可以做到这一点它每轮只需要知道“当前已选集合”和“未选点”之间的最小边而这条边只用比较刚加入的点与所有未选点的距离即可。这样我们完全不用事先存边边权随时算随时扔内存瞬间降到 O(n)。3. 算法选型完全图场景下 Prim 比 Kruskal 更趁手3.1 Kruskal 的排序瓶颈先说说为什么我在这个题里不首选 Kruskal。Kruskal 的流程是把所有边按边权从小到大排序然后用并查集依次尝试合并。放到完全图里n 个地牢加入口一共 n1 个点边数是 n(n1)/2。n1000 时边数约 50 万排个序倒也不算灾难50 万条边排序在 C 里也就是几十毫秒的事。真正的瓶颈在于要拿到这 50 万条边你必须先把每对节点之间的汉明距离算一遍。每对节点要扫 m 个字符总复杂度是 O(n²m)。光这一项n1000、m1000 就是 10 亿次字符比较存边还要 50 万条边的大数组。就算 10 亿次比较勉强能跑完后面 Kruskal 的排序和并查集同样还要再来一轮整体时间相当紧张。当然如果这道题把 n 出到 10000Kruskal 在完全图上的边数就是千万级别完全不可行。所以 Prim 是更稳的选择。3.2 不建图也能跑的 PrimPrim 算法的经典实现有两种一种是用优先队列优化适合稀疏图另一种是用一个 dist 数组维护“每个未选点到已选集合的最小距离”每轮 O(n) 找最小适合稠密图。这道题显然走第二种。伪代码大概是这样从入口节点 0 开始已选集合里只有 0。维护 dist[i] 表示地牢 i 到已选集合的最短边权。初始时 dist[i] 就等于地牢 i 直接连入口的代价也就是密码串里非 a 字符的数量。每一轮找出 dist 最小的未选地牢 u把它加入已选集合累加 dist[u] 到答案。然后用 u 去更新其它未选地牢的 dist新边权是 u 和那个地牢的汉明距离乘 w如果比当前 dist 小就更新。重复 n 次直到所有地牢都被选完。这个流程最关键的性质是每轮只需要检查新加入的节点 u 对其它未选点的边权就能保持 dist 数组正确。因为 dist 记录的是“到已选集合的最小值”而已选集合只新增了 u 一个点其它已选点的贡献之前已经处理过了不需要重新扫描。这比每次全部重算一遍已选集合的边快了一个数量级。3.3 初始化 dist 数组的特殊之处很多 Prim 模板的初始化都是把 dist 全部设为 INF然后随便选一个起点开始。这题不能照抄入口节点 0 从一开始就在集合里所以地牢的初始 dist 不是 INF而是它连到 0 号点的边权。这个初始化的语义一定要想清楚在 Prim 刚开始时已选集合里只有入口任何地牢想到达已选集合唯一的途径就是直接连入口。因此 dist[i] 初始值 密码串中与 a 不同的字符数。有的人喜欢把入口也当成一个正常节点先选 0再跑常规 Prim。那样也可以初始化时 dist 数组先存的是所有点到 0 的边权选完 0 后再正常更新。殊途同归只要记得 0 号点已经默认被选循环只需要执行 n 次而不是 n1 次。4. 完整 C 实现与 par 数组输出方案4.1 核心代码下面是我最后提交的 C17 版本。核心逻辑完全按照上面说的 Prim 来实现没有建边表没有堆所有边权都是按需计算的。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k, w; cin n m k w; vectorstring s(n 1); for (int i 1; i n; i) { cin s[i]; } const int INF 1e9; vectorint dist(n 1, INF); vectorint par(n 1, 0); vectorbool used(n 1, false); // 入口是节点 0密码串等效为 aaaa...a // 初始距离就是每个地牢到入口的距离非 a 的字符数 for (int i 1; i n; i) { int diff 0; for (char c : s[i]) { if (c ! a) diff; } dist[i] diff; par[i] 0; } long long ans 0; // 入口已经算作已选节点所以只需要再选 n 个地牢 for (int iter 0; iter n; iter) { int u -1; for (int i 1; i n; i) { if (!used[i] (u -1 || dist[i] dist[u])) { u i; } } used[u] true; ans dist[u]; // 用新加入的 u 更新未选点到已选集合的距离 for (int i 1; i n; i) { if (used[i]) continue; int diff 0; for (int p 0; p m; p) { if (s[u][p] ! s[i][p]) diff; } int cost diff * w; if (cost dist[i]) { dist[i] cost; par[i] u; } } } cout ans \n; for (int i 1; i n; i) { cout par[i] \n; } return 0; }4.2 边权计算与 Prim 循环逐行拆解代码里最容易被忽略的是第一阶段的初始化循环。很多模板会用dist.assign(n, INF)然后从点 1 开始跑但这题入口默认已在集合内所以必须把 dist 初始化为“到入口的代价”否则第一轮选出的点会是 INF答案直接变成垃圾数据。这里我用了par[i] 0作为默认的父节点因为初始时每个点都是通过入口进入网络的。选点循环的时间复杂度是 O(n)每轮扫一遍所有未选地牢选出 dist 最小的那个。这个操作在 n1000 时只有一百万次级别完全可以忽略不计。真正花时间的是后面的更新循环对于每个未选地牢要扫描 m 个字符数出哈明距离。这个循环每轮执行约 n 次每次 O(m)三轮下来就是 O(n²m)。出题人把 m 放在 1000 的量级就是为了让你用这个朴素实现也能跑过去。如果你想继续优化第 5 章会讲几个实际可用的方向。4.3 输出方案为什么 par 数组记录的边就是树边很多同学写完 Prim 后不知道怎么输出方案。这里的关键是维护一个 par 数组par[i] 表示地牢 i 是“因为连到了哪个点才以当前最小代价进入已选集合”。在 Prim 中当一个点 u 被选进集合时边 (u, par[u]) 就是最终生成树里的一条边u 的父节点就是 par[u]。注意这里的父子关系是“从入口长出去”的方向。因为入口 0 的 par 没有定义所有直接连入口的地牢 par[i]0如果一个地牢通过连到另一个地牢 j 进入网络那么 par[i]j。最终生成树的边集就是 { (i, par[i]) | 1 ≤ i ≤ n }。输出就按要求逐个打印 par[i] 就行。这个数组天然满足输出要求不需要再做 DFS 或重建树结构。我自己第一次实现时还想先把生成树建成邻接表再输出纯属多此一举后来发现 par 就够了。5. 复杂度、实测表现与 m 增大的优化方向5.1 O(n²m) 在本题约束下的实际表现朴素实现的总复杂度是 O(n² n²m)其中 O(n²) 是选点操作O(n²m) 是字符比较。n 和 m 都是 1000字符比较次数大约是 n(n-1)/2 × m差不多 5 亿次。这个数字看起来很大但在 C 里只是简单的 char 比较加上ios::sync_with_stdio(false)和cin.tie(nullptr)加速后本地实测 1 秒到 2 秒之间能跑完。Codeforces 这类题时限一般至少两秒所以朴素写法是安全的。这也是为什么我第一版直接这么交没有去做花式优化。真心建议在数据范围允许的情况下先写最朴素、最容易读的版本交一发自测不要一上来就上优化增加写错概率。5.2 字符比较改成整数比较的微优化如果你想进一步压时间最直接的优化是把 char 比较换成整数比较。输入时把每个字符串预处理成vectorint字符减 a 转成 0 到 25 的整数计算汉明距离时改为比较两个 int 数组。这样做能减少一点内存中的字节操作理论上会快一些但实测提升有限最多十个点左右的常数。另一个常见技巧是把字符串按 m 个字符拆成多个 64 位整数块每个字符用 5 或 6 位加上标记位压缩然后用异或和查表法统计差异块。这个优化虽然能大幅加速但代码复杂度上升很快而且你需要自己写查表很容易出 bug。在这题的数据范围里我强烈不建议为了赶时间上这种操作。5.3 如果把 m 放大向量集合 MST 的进阶思路如果这道题的 m 放大到 10 万级别朴素 O(n²m) 就完全不可行了。这时候题目性质会发生本质变化——你面对的不再是一堆字符串而是一个高维向量集合边权是向量间的汉明距离。这时候可以考虑的路线有这么几条按字符位置分组维护每个位置的字符分布用 bitset 记录地牢集合批量计算与某个地牢的汉明距离。这类方法能把 m 的维度摊到 bitset 的位运算里但实现难度陡增。如果字符集很小且 w 取特殊值可以尝试分析边权结构看是否能用更省内存的方式表示边权比如预计算所有地牢按某个维度排序在相邻点之间建候选边再跑 Kruskal这有点类似曼哈顿距离下的 MST 套路。如果只是求近似解或者数据规模大到出题人都会爆那基本不会出现在 CF 的常规 Div2 C 题里不用考虑。把 k 和 m 放到 1000 级别本身就是出题人留给选手的窗口让你可以用朴素 Prim 过但如果你选了错误的数据结构去存所有边就会在内存和时间上被卡死。这也是这道题想考察的核心能力之一。6. 踩坑记录WA 了四发之后我确认的细节6.1 忘记虚拟根节点只对 n 个地牢跑 MST这个错误非常隐蔽。我第一版代码是对 1 到 n 的地牢直接跑 Prim把 dist 初始化成它们之间的边权。输出的答案比样例小一圈因为所有边权都乘了 w而且没有任何地牢付出连入口的代价。正确姿势是永远把 0 号点放在集合里。它改变的不仅是边权的存在还改变了 Prim 的迭代次数。如果你直接在 1 到 n 上跑即使你算上了入口边权写出来的更新逻辑也会乱。我把这道题重新建模成 n1 个点的 MST 之后代码突然就短了一半。6.2 把“非 a 字符数”统计反了另一个让我翻车的地方是统计到入口的代价。我一开始写的是if (c a) diff;把基准串当成全是 b 来算了结果所有入口代价完全相反。这个错误手算样例时特别容易漏掉因为样例里地牢和基准串的差异刚好是对称的倍数关系前后答案看起来还挺自洽只有提交时才会炸。这类字符方向的坑可以用一个办法彻底规避不要写“统计什么不是基准”而是写“把入口当成第 0 个字符串然后用同一个汉明距离函数计算”。也就是把入口的密码串aaaa...a放到s[0]里所有边权统一调用calc_diff(s[u], s[i])函数要不要乘 w 另说。这样统一处理从逻辑上就杜绝了写反的可能。6.3 dist 更新没有跳过已选点导致边权被错误覆盖在更新循环里我曾经忘了加if (used[i]) continue;。表面上看问题不大已选点被更新也无所谓反正后面选点时会跳过它。但这里有个隐患如果已选点的 dist 被一个更大的值覆盖了后来某个未选点又把它当成参考对象去更新逻辑就会混乱。更严重的是出题数据如果精心构造已选点的“假更新”可能让 par 指向一个已经不在最优路径上的节点输出方案时用户的连接关系就会错。虽然答案可能还是对的但方案错了照样 WA。写 Prim 时更新循环里的used判断是一个不能省的细节。6.4 方案输出与树的父子关系混为一谈最后还有一个容易忽略的点输出 par 数组时很多人会下意识想把“树根的深度”或者“最终树的父子关系”调整成某种顺序其实完全没必要。题目只要求给出一组合法的连接方案par 数组天然就是方案。我刚开始想的是输出 DFS 序或者按层输出浪费了不少时间。后来才意识到对于一个 MST任意一棵树的边集都满足“每个非根节点有一条连向父节点的边”所以直接按编号输出 par 就是合法方案。这里不必纠结输出顺序题目一定接受任意可行解。7. 这类包装题的破题套路从“对象差异”到边权7.1 最关键的识别信号做完这道题后我特意总结了一套识别“伪字符串 MST 题”的方法。最关键的信号有三个有 n 个对象对象之间可以任意建立连接或转换关系。任意两个对象之间都能算出一个代价而且代价通常和某种“差异”正相关。目标是让所有对象连通或者让所有对象都达到某种统一状态求最小总代价。只要这三个条件同时满足十有八九就是最小生成树。不要被对象属性里的数组、字符串、坐标迷惑先把对象抽象成点代价抽象成边权再看连通约束是什么。7.2 三个同类变体第一类变体是“属性向量版本”每个对象带一个多维属性向量两个对象的边权是属性差的某种范数或汉明距离。本题就是这一类的典型只是属性刚好是字符串。第二类变体是“标准状态版本”题目指定一个标准对象或基准状态每个普通对象可以以某个代价直接变成标准状态也可以借由其它对象间接达到标准状态。这时候别忘了把基准状态也当节点等效于给 MST 加了一个虚拟根。这题入口就是标准状态。第三类变体是“互相转换版本”对象之间可以互相转化转化代价满足对称性问把所有对象归一到一起的最小代价。如果转化代价还满足三角不等式那答案往往就是一个 MST 或类似结构如果不满足可能就要往最短路或状态压缩方向想。这三类变体的共同核心都是先把每个对象看成图上的一个点再思考哪些边是候选边最后用 MST 或相关算法求解。7.3 总结成一句话的建模口诀建模的时候我心里会默念一句话“如果题目里有若干个东西每两个东西之间都有一个代价最终目标是让所有东西连通那就把它当成最小生成树来画图。”这句话帮我秒杀过好几道看似复杂的 CF 题。另外还有一个小技巧遇到不清楚建模对不对的题目拿一个很小的样例比如三个对象手动画图看看最优解是长链还是星形再对比是 MST 的形态还是最短路树。很多时候一眼就能判断要不要带入口节点以及边权要不要加系数。我个人对这道题最深的印象反而不是算法本身而是“入口全 a 字符串”这个巧妙的统一。它把两种看似不同的边权合并成了一种让整个问题从字符串题彻底变成图论题。后来我做别的题目时也会下意识去找这种“统一建模”的切入口往往能找到更干净的解法。如果你也在补题建议别急着看题解先自己把入口设成第 0 个节点试试——这个建模转折比任何代码细节都更值钱。