这是一道运用Prim算法求解最小生成树问题的题目，通过构建图的模型，计算使所有矿井获得电力供应的最小花费。以下是详细题解：

题目分析

题目要求为(n)口矿井提供电力供应，有两种供电方式：在矿井(i)上建立发电站，费用为(v_i)；在矿井(i)与已有电力供应的矿井(j)之间建立电网，费用为(p_{i,j}) 。目标是找到一个方案，使所有矿井都能获得电力供应且花费最小。可将每口矿井看作图中的节点，建立发电站或电网的费用看作边的权重，转化为求图的最小生成树问题。

代码逐段分析

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int n;
int w[N][N];
int dist[N];
bool st[N];

• 引入必要的头文件，cstdio用于标准输入输出，cstring用于字符串操作（这里主要用memset），iostream用于输入输出流，algorithm用于一些算法操作（如min函数）。
• 定义常量N表示节点的最大数量。
• 声明变量n记录矿井总数。
• 二维数组w[N][N]用于存储图中节点之间边的权重，即建立电网的费用或者建立发电站的费用。
• 数组dist[N]记录每个节点到已确定在最小生成树中的节点集合的最短距离。
• 布尔数组st[N]用于标记节点是否已被加入到最小生成树中。

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[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 || dist[t] > dist[j]))
                t = j;
        st[t] = true;
        res += dist[t];

        for (int j = 0; j <= n; j ++ ) dist[j] = min(dist[j], w[t][j]);
    }

    return res;
}

• prim函数实现了Prim算法：
  • memset(dist, 0x3f, sizeof dist); 将dist数组初始化为一个很大的值，这里0x3f3f3f3f常被用作表示无穷大。dist[0] = 0; 初始化第一个节点（这里虚拟了一个节点0来代表建立发电站的情况）到自身的距离为0。
  • 外层for循环进行(n + 1)次迭代，每次找到一个距离已确定在最小生成树中的节点集合最近的未访问节点。
  • 内层for循环遍历所有节点，找到未被访问且距离最小的节点t。
  • st[t] = true; 将找到的节点t标记为已访问，加入到最小生成树中。res += dist[t]; 将该节点到最小生成树的距离累加到结果res中。
  • 最后一个内层for循环更新其他未访问节点到最小生成树的距离，取原距离和当前节点t到其他节点距离的较小值。
  • 最终返回最小生成树的总权重res。

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &w[0][i]);
        w[i][0] = w[0][i];
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%d", &w[i][j]);

    printf("%d\n", prim());

    return 0;
}

• main函数是程序的入口：
  • scanf("%d", &n); 读取矿井的数量n。
  • 第一个嵌套for循环读取在每个矿井上建立发电站的费用，将其存储在w[0][i]和w[i][0]中，这里将建立发电站的情况看作是虚拟节点0与矿井节点之间的边。
  • 第二个嵌套for循环读取矿井之间建立电网的费用，存储在w[i][j]中。
  • 调用prim函数计算最小花费，并输出结果。
  • 程序结束，返回0。

时间复杂度分析

• Prim算法中，每次寻找距离最小的未访问节点需要遍历所有节点，时间复杂度为(O(n))，一共进行(n + 1)次，这部分时间复杂度为(O(n^2))。
• 更新其他节点到最小生成树的距离也需要遍历所有节点，每次时间复杂度为(O(n))，同样进行(n + 1)次，时间复杂度为(O(n^2))。
• 整体时间复杂度为(O(n^2))，其中(n)为矿井（节点）的数量。

空间复杂度分析

• 二维数组w[N][N]用于存储图的边权重，空间复杂度为(O(n^2))。
• 一维数组dist[N]和st[N]用于辅助计算，空间复杂度均为(O(n))。
• 整体空间复杂度为(O(n^2))。