【题目描述】发展采矿业当然首先得有矿井小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 n 口矿井但他似乎忘记考虑的矿井供电问题……为了保证电力的供应小 FF 想到了两种办法在这一口矿井上建立一个发电站费用为 v发电站的输出功率可以供给任意多个矿井。将这口矿井与另外的已经有电力供应的矿井之间建立电网费用为 p。小 FF 希望身为「NewBe_One」计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。【输入】第一行一个整数 n表示矿井总数。第 2∼n1 行每行一个整数第 i 个数 vi 表示在第 i 口矿井上建立发电站的费用。接下来为一个 n×n 的矩阵 p其中 pi,j 表示在第 i 口矿井和第 j 口矿井之间建立电网的费用数据保证有pi,jpj,i​ 且 pi,i0。【输出】输出仅一个整数表示让所有矿井获得充足电能的最小花费。【输入样例】4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0【输出样例】9【提示】样例解释小 FF 可以选择在 4 号矿井建立发电站然后把所有矿井都不其建立电网总花费是 32229。数据范围:对于 30% 的数据1≤n≤50对于 100% 的数据1≤n≤300,0≤vi,pi,j≤10^5​​ 。1. 题意转换本题本质上是在求将“点权”自身建站费用转化为“边权”后在一个包含N1个节点含1个虚拟的超级源点的完全无向图中求解最小生成树的总边权。2. 思考过程与解题思路第一直觉的暴力解法是什么如果不做模型转化我们会发现题目中既有“点权”自己建站又有“边权”互相拉电线。传统的 Kruskal 或 Prim 算法只能处理纯粹的边权图。第一直觉的暴力思路是利用 DFS 或状态压缩枚举所有“建站”的矿井子集选或不选然后在剩下的点集里跑最小生成树求拉线费用。为什么会 TLE因为有N个矿井枚举子集的时间复杂度是O(2^N)。本题的运算量早已突破天际必然会严重超时。考点锁定关键字“保证所有矿井电力供应的最小花费”强烈暗示了最小生成树模型连通所有点且代价最小。冲突点如何同时处理建站点权和拉线边权由此联想到图论中处理点权的最经典套路——超级源点虚拟节点建模。如何一步步推导到正解我们需要将“点权”降维成“边权”。不妨在天空中虚拟出一座无尽的“上帝发电站”将其编号为0号节点。在第i个矿井建站花费在物理意义上完全等价于花的钱从0号节点拉一根电线到i号矿井。如此一来不论是“自己建站”还是“与别人拉线”全都变成了“连边”。现实中所有合法的通电方案都完美等价于这N1个点构成的一棵生成树因为树连通意味着所有矿井最终都直接或间接地连到了0号节点保证全部有电。问题瞬间蜕变为裸的最小生成树。3. 算法设计与样例推演核心逻辑与数据结构Kruskal 算法通过贪心策略按边权从小到大加边利用并查集判环最适合这类边数较多且需要加边的场景。边集数组edge存储两类边一类是的建站边另一类是的电网边。并查集DSUfa数组用于在贪心加边时判断两个矿井是否已经在同一个连通块或是否都已通电防止产生冗余的环。样例手玩推演给定 4 个矿井。建站费用为。建立超级源点边提取矩阵有效边拉线费用Kruskal 贪心排序并选边选 (1,2,2)花费 2。连通块选(1,3,2)花费 2。连通块选(1,4,2)花费 2。连通块选(0,4,3)花费 3。连通块(全部通电)此时已选够4条边提前结束。总花费。与样例输出完全一致。4. 时空复杂度分析时间复杂度。图中有N1个点由于是完全图优化后边数。对于边数。Kruskal 的瓶颈在sort排序次运算C 在 1 秒内能跑10^8次时间极其充裕。空间复杂度O(E N)。边集数组长度约为45000并查集数组长度为310。整体内存消耗极低约 1MB远低于题目要求的64MB限制可以通过。5. 坑点与易错总结超级源点0号的初始化由于多了一个虚拟节点并查集的初始化必须从0开始for(int i0; in; i)漏掉0会导致涉及建站的边全部合并失败。无向图矩阵的双倍冗余题目给定的矩阵是对称的。如果不加控制直接全盘读入会导致相同权值的边被存入两次让sort耗时翻倍。边数判定提前退出N1个点的图生成树只需要N条边不加break判断会白白遍历大量废边。6. 代码进阶与优化剖析核心教学点审视下方提供的代码可以说这份代码已经是一份无可挑剔的金牌级模板。它完美避开了上述所有的坑点。这里提炼出代码中极具价值的2 个高阶编码习惯供大家学习高阶技巧 1矩阵遍历中的“半角过滤”在处理电网费用的双重循环中代码使用了if(ji)。这是一个非常绝妙的常数优化。对于对称矩阵对角线ij是无用数据自己连自己而ji的左下三角与右上三角完全重复。通过ji直接过滤掉了一半以上的无效与重复边极大减轻了后续sort的压力彰显了扎实的代码功底。高阶技巧 2Kruskal 的“早退机制”代码中引入了int cnt 0;计数器并在循环末尾加上了if(cnt n) break;。在含有几万条边的稠密图中前几百条边通常就能把树建好剩下的几万条边如果继续执行find(a) ! find(b)会带来极大的常数开销。这个break是标准的工业级 MST 写法极致压榨了运行常数。7. 完整代码//最小生成树 //建立一个0号点 所有需要自己建立发电站的矿井就相当于和0号点连边 #include iostream #include algorithm using namespace std; int n; int idx;//总边数 //边集数组 struct edge{ int u; int v; int val; //按照费用从小到大排序 friend bool operator (edge a,edge b){ return a.valb.val; } }e[92000]; int fa[310];//fa[i]代表i节点的集合中的老大 long long sum;//总最小花费 //并查集搜索并进行路径压缩 int find(int x){ if(fa[x]x) return x; return fa[x]find(fa[x]); } //并查集连接 void uni(int a,int b){ int faafind(a); int fabfind(b); if(faa!fab){ fa[faa]fab;//让b的祖先成为a祖先的祖先 完成连通块合并 } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; //初始化所有点的老大是自己 0号源点不要忘记了 for(int i0;in;i) fa[i]i; //先把每个矿井上建边分别需要多少费用存进边集数组 //即把每个点与0号点相连存进边集数组 for(int i1;in;i){ idx; e[idx].u0; e[idx].vi; cine[idx].val; } //接下来吧所有矿井和矿井之间建立电网的费用存进去 for(int i1;in;i){ for(int j1;jn;j){ int s; cins; //这里写i!j也可以 但就存了一半的重复的边进去 很浪费时间sort) if(ji){ idx; e[idx].ui; e[idx].vj; e[idx].vals; } } } //对边集数组按费用从小到大排序 sort(e1,eidx1); int cnt0;//记录成功连接的边数 //接下来遍历边集数组 for(int i1;iidx;i){ int ae[i].u; int be[i].v; //如果a和b不在一个联通分量中 就把它两连接 并把边权计算进总花费 if(find(a)!find(b)){ uni(a,b); sume[i].val; cnt;//成功连上一条边 } //n1个点的图 生成树只有n条边 if(cntn) break;//最多能连n条边 连完以后就可以退出了 } coutsum; return 0; }