企业官网建设流程全解析

看到 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 的选择过程。

假设 n=3，m=4，w=1，三个密码串分别是：

1: bbbb 2: bbbc 3: bbcc

入口 0 对应的串是aaaa。先算所有点到入口的代价：

• 地牢 1：bbbb和aaaa四个位置全不同，代价 4
• 地牢 2：bbbc和aaaa四个位置全不同，代价 4
• 地牢 3：bbcc和aaaa四个位置全不同，代价 4

再算地牢之间的汉明距离：

• 1 和 2：只有第 4 位不同（b 对比 c），差距 1，乘 w 后代价 1
• 1 和 3：第 3、4 位不同，差距 2，代价 2
• 2 和 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' 的地牢，然后对所有 n+1 个点跑 MST。我见过不少人在这里翻车：对 n 个地牢跑出一个小得离谱的答案，样例根本对不上，debug 半天才发现是把自己脑子里的贪心当成了题意。

2.3 这里的 MST 与普通 MST 的唯一区别：完全图边权按需生成

普通 MST 题通常会直接给你边集，大多数用 Kruskal 就能解决。这道题的特殊之处在于它是一张完全图——n 个地牢加上入口，两两之间都有边，边数大约是 n(n+1)/2。

完全图本身不可怕，关键是边权的计算方式是“实时生成”的：每两个节点之间的边权要扫描一遍长度为 m 的密码串才能算出来。理论上你可以先把所有边权算出来存成邻接表，再去跑 MST；但当 n 到 1000、m 也到 1000 时，预计算所有边权的时间和内存都不划算。

更好的做法是让 MST 算法自己按需取边权。恰好 Prim 算法可以做到这一点：它每轮只需要知道“当前已选集合”和“未选点”之间的最小边，而这条边只用比较刚加入的点与所有未选点的距离即可。这样我们完全不用事先存边，边权随时算随时扔，内存瞬间降到 O(n)。

3. 算法选型：完全图场景下 Prim 比 Kruskal 更趁手

3.1 Kruskal 的排序瓶颈

先说说为什么我在这个题里不首选 Kruskal。Kruskal 的流程是把所有边按边权从小到大排序，然后用并查集依次尝试合并。放到完全图里，n 个地牢加入口一共 n+1 个点，边数是 n(n+1)/2。n=1000 时边数约 50 万，排个序倒也不算灾难，50 万条边排序在 C++ 里也就是几十毫秒的事。

真正的瓶颈在于：要拿到这 50 万条边，你必须先把每对节点之间的汉明距离算一遍。每对节点要扫 m 个字符，总复杂度是 O(n²m)。光这一项，n=1000、m=1000 就是 10 亿次字符比较，存边还要 50 万条边的大数组。就算 10 亿次比较勉强能跑完，后面 Kruskal 的排序和并查集同样还要再来一轮，整体时间相当紧张。

当然，如果这道题把 n 出到 10000，Kruskal 在完全图上的边数就是千万级别，完全不可行。所以 Prim 是更稳的选择。

3.2 不建图也能跑的 Prim

Prim 算法的经典实现有两种：一种是用优先队列优化，适合稀疏图；另一种是用一个 dist 数组维护“每个未选点到已选集合的最小距离”，每轮 O(n) 找最小，适合稠密图。这道题显然走第二种。

伪代码大概是这样：

1. 从入口节点 0 开始，已选集合里只有 0。
2. 维护 dist[i] 表示地牢 i 到已选集合的最短边权。
3. 初始时 dist[i] 就等于地牢 i 直接连入口的代价，也就是密码串里非 'a' 字符的数量。
4. 每一轮找出 dist 最小的未选地牢 u，把它加入已选集合，累加 dist[u] 到答案。
5. 然后用 u 去更新其它未选地牢的 dist：新边权是 u 和那个地牢的汉明距离乘 w，如果比当前 dist 小就更新。
6. 重复 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 次而不是 n+1 次。

4. 完整 C++ 实现与 par 数组输出方案

4.1 核心代码

下面是我最后提交的 C++17 版本。核心逻辑完全按照上面说的 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; vector<string> s(n + 1); for (int i = 1; i <= n; i++) { cin >> s[i]; } const int INF = 1e9; vector<int> dist(n + 1, INF); vector<int> par(n + 1, 0); vector<bool> 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 最小的那个。这个操作在 n=1000 时只有一百万次级别，完全可以忽略不计。真正花时间的是后面的更新循环：对于每个未选地牢，要扫描 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 比较换成整数比较。输入时把每个字符串预处理成vector<int>，字符减 '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 上跑，即使你算上了入口边权，写出来的更新逻辑也会乱。我把这道题重新建模成 n+1 个点的 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 个节点试试——这个建模转折比任何代码细节都更值钱。