Prim算法

朴素Prim算法，时间复杂度O(n2)
堆优化版不如直接用Kruskal

要素

1. g[][]邻接矩阵，存储图的信息
2. st[]记录已经在集合中的点

3. dist[] 存储每个点到集合的最短距离

   思路

   非常像朴素版Dijkstra算法

4. Arrays.fill[dist, INF]; dist[1] = 0

5. for(i : 1~n)

遍历各个节点，找到
t <- 不在st中的距离集合最近的点
st <- t加入该点到st
遍历t的临边，更新临点到集合的最短距离

证明：
假设不选当a前边得到最终的生成树。然后将这条边加上，必然会出现一个环，在这个环上一定可以找出一条长度不小于当前边的边b，用a替换b结果一定不会更差

模板

858. Prim算法求最小生成树

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤500,
1≤m≤105
图中涉及边的边权的绝对值均不超过 10000。
输入样例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

6

import java.util.*;
public class Main {
    static int n, m;
    static int[][] g;
    static final int INF = 0x3f3f3f3f;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        g = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(g[i], INF);
        }
        while (m-- > 0) {
            int a, b, w;
            a = sc.nextInt();
            b = sc.nextInt();
            w = sc.nextInt();
            g[a][b] = Math.min(g[a][b], w);
            g[b][a] = Math.min(g[b][a], w);
        }
        int res = prim();
        if (res == INF) System.out.println("impossible");
        else System.out.println(res);
    }
    static int prim() {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, 0x3f3f3f3f);
        boolean[] st = new boolean[n + 1];
        int res = 0;
        dist[1] = 0;
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }
            if (dist[t] == INF) return INF;
            res += dist[t];
            st[t] = true;
            for (int j = 1; j <= n; j++) {
                if (dist[j] > g[t][j]) {
                    dist[j] = g[t][j];
                }
            }
        }
        return res;
    }
}