从一道 CSP-S 真题出发：聊聊带可选扩展点的最小生成树

题源洛谷 P14362 [CSP-S 2025] 道路修复想象一下你是一位城市规划师手里有一张地图上面画着n nn座城市和m mm条被地震震断的道路。修复每条路都要花钱而且价格不菲。更棘手的是地图上还有k kk个偏远的乡镇你可以选择花一笔钱把它们升级成城市升级之后就能从那里向周围的城市修新路。问题是怎么花最少的钱让地图上所有城市重新连成一片这道题来自 2025 年 CSP-S 第二轮表面上是一个图论题实际上它考察的是**在经典最小生成树MST框架下如何优雅地处理可选扩展点**这一核心思想。本文将带你从直觉出发逐步拆解这道题的解法并把它沉淀成一个可以复用的算法模板。一、问题本质不是修路而是做选择很多同学拿到这道题第一反应是这不就是最小生成树吗“——对了一半。如果只是修复原有道路那确实是裸的 MST。但题目加了一个关键变量乡镇是可以选择改造或不改造的。改造一个乡镇相当于解锁了一组新的边从该乡镇到各个城市的道路但要先付一笔入场费”c j c_jcj​。这就好比你去商场买东西有些店铺是免费逛的原有道路有些店铺需要先买会员卡才能进改造乡镇会员卡本身有价格但进去之后可能买到特别便宜的商品低费用的乡镇到城市道路。你要做的就是在买哪些会员卡和买哪些商品之间做最优组合。这道题的核心特征可以概括为以下几点连通性约束最终必须保证n nn座城市两两连通这是硬约束可选扩展点k kk个乡镇是可选的改造与否完全由费用决定边分类原有道路始终可用乡镇到城市的边只有在改造该乡镇后才可用组合爆炸k kk个乡镇有2 k 2^k2k种改造组合需要高效枚举规模暗示k ≤ 10 k \leq 10k≤10从代码中c [ 15 ] c[15]c[15]和1 k 1k1k可以推断2 k 1024 2^k 10242k1024完全可接受所以这道题的本质是在 MST 的框架下通过枚举可选扩展点的状态寻找全局最优的连通方案。二、解题策略基准 增量枚举所有可能面对可选扩展点的问题最自然的思路是先求一个基准解再考虑增量优化。具体来说阶段一求基准 MST。不考虑任何乡镇只用m mm条原有道路跑 Kruskal得到一个基准费用。这相当于什么都不做的保底方案。阶段二预处理扩展边。对每个乡镇j jj读入改造费用c j c_jcj​和到各城市的建路费用a j , i a_{j,i}aj,i​把这些边统一存储起来并标记它们属于哪个乡镇。阶段三枚举改造状态。因为k ≤ 10 k \leq 10k≤10可以直接二进制枚举2 k 2^k2k种状态。对每个状态累加被改造乡镇的改造费用然后把原有 MST 边 该状态下可用的乡镇边一起跑 Kruskal求 MST 费用取全局最小值。这个策略的关键在于原有道路的 MST 边只有n − 1 n-1n−1条把它们和乡镇边放在一起排序后每次枚举只需要重新跑一次 Kruskal复杂度完全可控。三、算法模板带条件边的 Kruskal3.1 算法到底在干什么—— 直觉解释Kruskal 算法的核心思想可以用一句话概括每次选最便宜的边只要不形成环就选。它就像一位精打细算的采购员手里有一份所有商品边的价格清单每次挑最便宜的买但一旦发现买了会让手里已有的商品形成闭环即连通块内已经有通路就果断放弃。在本题中我们给这位采购员增加了一条规则有些商品乡镇边需要先付会员费改造费用才能购买。于是采购员的流程变成决定买哪些会员卡枚举改造状态付会员卡的钱在可购买的商品中继续按 Kruskal 的规则挑选最便宜的边比较所有会员卡组合的总花费选最便宜的3.2 万能模板 —— 伪代码 实战代码伪代码function KruskalWithOptionalNodes(edges, optionalNodes, state): totalCost 0 edgeCount 0 // 累加被选中可选节点的激活费用 for each node in optionalNodes: if state 包含该节点: totalCost node.activationCost totalNodes // 初始化并查集 for i 1 to totalNodes: parent[i] i // 遍历所有边按费用排序 for each edge in sortedEdges: if edge 属于某个可选节点: if state 不包含该节点: continue // 该边不可用 if find(edge.u) ! find(edge.v): union(edge.u, edge.v) totalCost edge.cost edgeCount if edgeCount totalNodes - 1: break // 已形成生成树 if edgeCount totalNodes - 1: return INF // 不连通 return totalCost实战代码C#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN1000515,M1100005,INF1e18;intn,m,k,ans1e18;intp[N];// 并查集父节点数组intc[15];// 每个乡镇的改造费用structEdge{inta,b,w,idx;// idx0表示原有道路idx0表示属于第idx个乡镇booloperator(constEdgeE)const{returnwE.w;}}edges[M],newedges[M];intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}// 阶段一求只考虑原有道路的基准MSTintkruskal(){sort(edges1,edgesm1);for(inti1;in;i)p[i]i;intres0,cnt0;for(inti1;im;i){intaedges[i].a,bedges[i].b,wedges[i].w;afind(a),bfind(b);if(a!b){p[a]b;resw;cnt;newedges[cnt]edges[i];// 保存MST边供后续使用}}if(cntn-1)returnINF;returnres;}// 阶段三在状态x下求带可选扩展点的MSTintkruskal2(intx){intsn;// 总点数 n个城市 被改造的乡镇数intres0,cnt0;inttmpx;for(inti1;ik;i){if(tmp1)// 第i个乡镇被改造{s;resc[i];}tmp1;}// 初始化并查集城市乡镇for(inti1;ink;i)p[i]i;// 遍历所有边MST边 乡镇边按费用排序for(inti1;im;i){// 条件判断乡镇边只有在对应乡镇被改造时才可用if(newedges[i].idx){inttmpx;for(intj1;jnewedges[i].idx;j)tmp1;if((tmp1)0)continue;}intanewedges[i].a,bnewedges[i].b,wnewedges[i].w;afind(a),bfind(b);if(a!b){p[a]b;resw;cnt;}if(cnts-1||resans)break;// 提前退出剪枝}if(cnts-1)returnINF;returnres;}signedmain(){cinnmk;for(inti1;im;i)cinedges[i].aedges[i].bedges[i].w;anskruskal();// 基准MSTmn-1;// 原有MST只有n-1条边// 阶段二读入乡镇信息生成扩展边for(inti1;ik;i){cinc[i];for(intj1;jn;j){intx;cinx;newedges[m].ani;// 乡镇节点编号为ninewedges[m].bj;newedges[m].wx;newedges[m].idxi;// 标记属于第i个乡镇}}sort(newedges1,newedgesm1);// 枚举所有改造状态for(inti1;i(1k);i){ansmin(ans,kruskal2(i));}coutansendl;return0;}3.3 例题实现 —— 本题完整代码上面的代码已经是本题的完整 AC 代码。核心流程可以概括为读入n , m , k n, m, kn,m,k和m mm条原有道路跑 Kruskal 求基准 MST保存 MST 边到newedges读入k kk个乡镇的信息生成乡镇到城市的边加入newedges对所有边排序枚举2 k 2^k2k种改造状态对每个状态累加改造费用跑带条件筛选的 Kruskal取全局最小值输出3.4 对比实现 —— 另一种思路Prim 算法可行吗理论上Prim 算法也可以解决 MST 问题。但在这道题中Kruskal 有明显优势对比维度KruskalPrim边排序全局排序一次枚举时直接复用每次需要重新维护堆条件边处理通过idx标记跳过不可用边需要动态维护邻接表并查集天然支持连通性判断需要额外标记代码复杂度更简洁相对复杂因此对于带条件边的 MST 问题Kruskal 是更优选择。3.5 变体清单 —— 这类问题的常见变形变体类型特征描述处理思路带强制节点的 MST某些节点必须被选中预处理强制费用枚举剩余可选节点分层扩展点扩展点有依赖关系如改造 A 后才能改造 B按拓扑序枚举或状态压缩 DP多组可选边集多组互斥的边集选一组枚举组的选择每组内部跑 MST节点容量限制每个扩展点最多连t tt条边在 Kruskal 中加入度数限制判断动态加边边按时间顺序出现离线处理按时间轴枚举3.6 什么时候不能用—— 边界条件和反例这个模板虽然好用但也有明确的适用范围k kk不能太大如果k 20 k 20k202 k 2^k2k枚举会变得不可行需要考虑其他算法如状压 DP、网络流原有图必须连通题目保证任意两座城市都能通过若干条道路相互到达如果去掉这个条件需要额外判断不连通的情况费用不能为负如果改造费用或边权为负Kruskal 的贪心策略仍然正确MST 允许负权边但需要注意int溢出问题不能有重边自环本题数据保证无重边自环如果有需要预处理四、底层逻辑为什么这个算法是对的4.1 Kruskal 的贪心正确性Kruskal 算法的正确性基于一个经典定理在 MST 中任意一个割的轻边跨越该割的最小权边必然属于某棵最小生成树。Kruskal 每次选择全局最小边本质上是在不断选择某个割的轻边因此最终得到的生成树一定是最小的。在本题中我们只是限制了某些边在特定条件下才能被选择但只要在可用边集中继续按 Kruskal 的规则选边贪心正确性依然成立——因为我们只是在可用的边这个子集上跑 Kruskal而 Kruskal 对任意边集都是正确的。4.2 枚举所有状态的必要性为什么不能贪心选择改造哪些乡镇因为改造一个乡镇的收益不是独立的。改造乡镇 A 可能让城市 1 和 2 连通的费用降低但改造乡镇 B 可能让城市 3 和 4 连通的费用降低而 A 和 B 的组合可能产生更优的协同效应。这种非独立性意味着没有简单的贪心规则必须枚举所有组合。幸运的是k ≤ 10 k \leq 10k≤10给了我们枚举的可能性。这提醒我们在竞赛中看到可选、“可选扩展”、可选设施这类关键词时首先要关注可选对象的数量——如果很小≤ 20 \leq 20≤20枚举往往是正解。4.3 提前退出剪枝的有效性代码中的if (cnt s - 1 || res ans) break;是一个重要的优化cnt s - 1生成树已经形成后续边不需要再考虑res ans当前费用已经超过已知最优解继续枚举只会更差这个剪枝在k kk较大或边权分布不均匀时效果尤为明显可以将实际运行时间降低一个数量级。五、决策表遇到这类问题怎么选算法场景特征推荐方案原因可选节点数k ≤ 15 k \leq 15k≤15二进制枚举 Kruskal枚举量可控实现简单可选节点数k 15 k 15k15但图很稀疏状压 DP 连通性预处理避免重复计算连通性可选节点有依赖关系拓扑排序 树形 DP处理依赖约束需要选恰好t tt个节点枚举组合数C ( k , t ) C(k,t)C(k,t) Kruskal减少枚举量边权动态变化离线排序 并查集维护避免重复排序需要输出具体方案在 Kruskal 中记录选边保存路径信息六、工程视角这个思想在实际中有什么用这道题虽然是竞赛题但其核心思想在工程中有广泛应用云计算资源调度在 AWS、阿里云等云平台中用户可以选择按需实例原有道路价格固定或预留实例乡镇改造先付一笔预付款获得更低单价。平台需要在满足所有业务需求的前提下最小化总成本。本题的思想可以直接迁移到这类混合资源调度问题中。5G 基站部署在城市中部署 5G 网络时有些区域可以直接利用现有光纤原有道路有些偏远区域需要先建设小型数据中心改造乡镇再从数据中心向周围辐射信号。如何以最低成本实现全网覆盖这正是带可选扩展点的 MST 问题。物流网络优化在构建物流网络时可以选择在一些城市建立区域分拨中心改造乡镇从分拨中心向周边城市配送。建立分拨中心有固定成本但后续配送成本更低。全局最优的网络结构需要权衡建不建分拨中心和怎么连配送路线与本题完全同构。七、小结这道题教会我们的核心认知可以概括为一句话当 MST 遇到可选扩展点时先求基准解再枚举所有扩展组合在每种组合下复用 Kruskal 的贪心策略最后取全局最优。用公式化语言总结最优费用 min ⁡ S ⊆ { 1 , 2 , … , k } ( ∑ j ∈ S c j MST ( E base ∪ E S ) ) \text{最优费用} \min_{S \subseteq \{1,2,\ldots,k\}} \left( \sum_{j \in S} c_j \text{MST}(E_{\text{base}} \cup E_S) \right)最优费用S⊆{1,2,…,k}min​​j∈S∑​cj​MST(Ebase​∪ES​)​其中S SS是被改造的乡镇集合E base E_{\text{base}}Ebase​是原有道路E S E_SES​是S SS中乡镇到城市的边MST ( ⋅ ) \text{MST}(\cdot)MST(⋅)表示对应边集的最小生成树费用。这道题的价值不仅在于它本身更在于它揭示了一类问题的通用解法当问题中出现可选设施、可选扩展点时首先判断可选对象的数量——如果可控枚举往往是最直接、最可靠的正解。在竞赛中这种规模暗示是破题的关键线索。