$$\color{Red}{新的开始【prim】-虚拟源点}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

发展采矿业当然首先得有矿井，小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 n 口矿井，但他似乎忘记了考虑矿井供电问题。

为了保证电力的供应，小 FF 想到了两种办法：

在矿井 i 上建立一个发电站，费用为 vi（发电站的输出功率可以供给任意多个矿井）。
将这口矿井 i 与另外的已经有电力供应的矿井 j 之间建立电网，费用为 pi,j。
小 FF 希望你帮他想出一个保证所有矿井电力供应的最小花费方案。

输入格式

第一行包含一个整数 n，表示矿井总数。

接下来 n 行，每行一个整数，第 i 个数 vi 表示在第 i 口矿井上建立发电站的费用。

接下来为一个 n×n 的矩阵 P，其中 pi,j 表示在第 i 口矿井和第 j 口矿井之间建立电网的费用。

数据保证 pi,j=pj,i，且 pi,i=0。

输出格式

输出一个整数，表示让所有矿井获得充足电能的最小花费。

数据范围

1 ≤ n ≤ 300

0 ≤ vi, pi , j ≤ 10 ^ 5

输入样例：

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

输出样例：

9

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8 为最佳。

n <= 100 -> O(n ^ 3) -> 状态压缩dp floyd 高斯消元

n <= 1000 -> O(n ^ 2) O(n ^ 2 * log(n)) -> dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford

n ≤ 100000 -> O(nlogn) -> 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa

我的SPFA全题解

我的Dijkstra全题解

我的Bellman_fold全题解

我的Floyd全题解

我的Prim题解

我的Kruskal题解

解析

这题的第一直觉，做 n次最小生成树，枚举每个点作为起点的情况，但是仔细想想，300次来看，即便加了堆优化也可能TL。

然后想到每次加起点的操作，有点麻烦，而且理论上感觉应该先加更短的边合理，进一步想，那直接建立虚拟源点，到每个点的距离就是建站花费，岂不是一次 prim 就解决问题？

因此这道题的思路就结束了。

易错点

一年前最初刷算法题遇到的一个坑，prim虽然和dijkstra一样，只不过把距离数组换成了距离树的距离，但是关键在于dijkstra枚举完n-1个点，就已经把最短距离算出来了，不需要枚举最后一个点。

而spfa每枚举一个点才会加一次边权，我们想获得生成树的总长，势必要加上最后一个点的，虽然它不会再更新任何边权和距离，但是我们外层的枚举i，一定要和点数相同，不能偷懒减一。

java

import java.util.*;
import java.io.*;


public class Main {

    static final int N = 310, INF = 0x3f3f3f3f;
    static int n;
    static int [] dist = new int [N];
    static int [][] g = new int [N][N];
    static boolean [] st = new boolean [N];

    static int spfa(){
        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 = 1; j <= n; j ++)
                dist[j] = Math.min(dist[j], g[t][j]);    
        }
        return res;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String [] args) throws IOException{
        Arrays.fill(dist, INF);
        n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i ++) g[0][i] = g[i][0] = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i ++){
            String [] s1 = br.readLine().split(" ");
            for (int j = 1; j <= n; j ++){
                g[i][j] = Integer.parseInt(s1[j-1]);
            }
        }
        System.out.println(spfa());
    }
}