题解 | #最小生成树#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        return new Prim2(n,m,cost).miniSpanningTree();
    }
}
class Prim2{
    static int INF = 0x3f3f3f3f;
    int n;
    int m;
    List<int[]>[]g;
    boolean[] vis;
    //点 距离
    PriorityQueue<int[]> pq = new PriorityQueue<int[]>((o1,o2)-> o1[1] - o2[1]);
    Prim2(int n, int m, int [][]cost){
        this.n = n;
        this.m = m;
        g = new List[n+1];
        Arrays.setAll(g, l -> new ArrayList());
        vis = new boolean[n+1];
        for(int[]tuple: cost){
            int x = tuple[0], y = tuple[1], w = tuple[2];
            g[x].add(new int[]{y,w});
            g[y].add(new int[]{x,w});
        }
    }
    public int miniSpanningTree(){
        int res = 0, cnt = 0;
        pq.add(new int[]{1,0});
        while(!pq.isEmpty()){
            int []pair = pq.poll();
            int x = pair[0], w = pair[1];
            if(vis[x]) continue;
            vis[x] = true;
            cnt++;
            res += w;
            //松弛邻居
            for(int []p: g[x]){
                int y = p[0], d = p[1];
                if(vis[y])continue;
                pq.add(new int[]{y, d});
            }
        }
        System.out.println(cnt == n);
        return cnt == n ? res : -1;
    }
}

class Prim{
    static int INF = 0x3f3f3f3f;
    int n;
    int [][] g; //邻接矩阵
    int []dist; //每个点到当前最小生成树的距离
    boolean []vis; //点是否在最小生成树中
    Prim(int n, int m, int [][]cost){
        this.n = n;
        vis = new boolean[n+1];
        g = new int [n+1][n+1];
        dist = new int[n+1];
        Arrays.fill(dist, INF);
        for(int[]arr: g) Arrays.fill(arr, INF);
        for(int []tuple:cost){
            int x = tuple[0], y = tuple[1], d = tuple[2];
            g[x][y] = g[x][y];
            g[y][x] = g[y][x];
        }
    }

    /**
        1.每次选择一个距离最小生成树距离最小的点
        2.松弛刚才选择的点邻居
    */
    public int miniSpanningTree(){
        int res = 0;
        dist[1] = 0;//以节点1为最小生成树的起点
        for(int i = 0; i < n; i++){
            //每次选择距离当前最小生成树最小的边
            int t = -1;
            for(int j = 1; j <= n; j++){
                if(vis[j]) continue;
                if(t == -1 || dist[j] < dist[t]) t = j;
            }
            //不联通
            if(i > 0 && (t == -1 || dist[t] == INF)) return -1;
            res += dist[t];
            vis[t] = true; 
            //松弛以t为出发点的到期邻居的距离
            for(int j = 1; j <= n; j++) if(!vis[j])dist[j] = Math.min(dist[j], g[t][j]);
        }
        return res;
    }
}


class Kruskal{
    int n ;
    int m;
    int[][] edges;
    int []p; // 并查集

    Kruskal(int n, int m , int [][]cost){
        this.n = n;
        this.m = m;
        p = new int[n+1];
        for(int i = 1; i <= n; i++) p[i] = i;
        edges = cost;
        Arrays.sort(edges, (o1, o2)-> o1[2] - o2[2]);
    }

    int find(int x){
        if(p[x] != x){
            p[x] = find(p[x]);
        }
        return p[x];
    }

    void merge(int x, int y){
        p[x] = y;
    }

    public int miniSpanningTree(){
        int res =0, cnt = 0;
        for(int i = 0; i < m; i++){
            int x = find(edges[i][0]), y = find(edges[i][1]), w = edges[i][2];
            if(x != y){
                merge(x,y);
                res += w;
                cnt++;
            }
        }
        return cnt == n - 1 ? res : -1;
    }
}