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