发展采矿业当然首先得有矿井，小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 n 口矿井，但他似乎忘记了考虑矿井供电问题。
为了保证电力的供应，小 FF 想到了两种办法：
在矿井 i 上建立一个发电站，费用为 vi（发电站的输出功率可以供给任意多个矿井）。 将这口矿井 i 与另外的已经有电力供应的矿井 j 之间建立电网，费用为 p i , j p_{i,j} pi,j。 小 FF 希望你帮他想出一个保证所有矿井电力供应的最小花费方案。
输入格式
第一行包含一个整数 n，表示矿井总数。
接下来 n 行，每行一个整数，第 i 个数 vi 表示在第 i 口矿井上建立发电站的费用。
接下来为一个 n×n 的矩阵 P，其中 p i , j p_{i,j} pi,j表示在第 i 口矿井和第 j 口矿井之间建立电网的费用。
数据保证 p i , j p_{i,j} pi,j= p j , i p_{j,i} pj,i，且 p i , i p_{i,i} pi,i=0。
输出格式
输出一个整数，表示让所有矿井获得充足电能的最小花费。
数据范围
1 ≤ n ≤ 300 , 0 ≤ v i , p i , j ≤ 105 1≤n≤300, 0≤vi,p_{i,j}≤105 1≤n≤300,0≤vi,pi,j≤105
输入样例：
4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0输出样例：
9分析：
由 题 意 ， 对 于 每 个 点 ， 可 以 在 该 点 投 入 一 定 花 费 ， 或 者 向 该 点 连 接 一 条 边 。 由题意，对于每个点，可以在该点投入一定花费，或者向该点连接一条边。 由题意，对于每个点，可以在该点投入一定花费，或者向该点连接一条边。
事 实 上 ， 我 们 可 以 建 立 虚 拟 源 点 0 号 点 ， 将 各 点 上 的 权 值 转 化 为 与 0 号 点 之 间 的 边 权 。 事实上，我们可以建立虚拟源点0号点，将各点上的权值转化为与0号点之间的边权。 事实上，我们可以建立虚拟源点0号点，将各点上的权值转化为与0号点之间的边权。
于 是 问 题 转 化 为 一 个 n + 1 个 点 的 最 小 生 成 树 问 题 。 于是问题转化为一个n+1个点的最小生成树问题。 于是问题转化为一个n+1个点的最小生成树问题。
代码:
#include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=310; int n; int w[N][N],dis[N]; bool st[N]; int prim() { memset(dis,0x3f,sizeof dis); dis[0]=0; int res=0; for(int i=0;i<n+1;i++) { int t=-1; for(int j=0;j<=n;j++) if(!st[j] && (t==-1 || dis[t]>dis[j])) t=j; st[t]=true; res+=dis[t]; for(int j=0;j<=n;j++) dis[j]=min(dis[j],w[t][j]); } return res; } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>w[0][i]; w[i][0]=w[0][i]; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>w[i][j]; cout<<prim()<<endl; return 0; }