3、Prim最小生成树

AcWing 858. Prim算法求最小生成树

Prim算法相比于Kruskal算法更加适用于稠密图

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int N = 510;
    int n, m;
    int g[][] = new int[N][N];
    int EXCEED = 10000010;
    HashSet<Integer> has_add = new HashSet();
    HashSet<Integer> other_point = new HashSet();
    int edge_value_sums = 0;

    void prim() {
        int start = 1;
        has_add.add(start);
        other_point.remove(start);

        while (has_add.size() < n) {
            int min = EXCEED;
            int min_point = -1;
            for (Integer other : other_point) {
                for (Integer has : has_add) {
                    if (g[other][has] < min) {
                        min = g[other][has];
                        min_point = other;
                    }
                }
            }
            if (min_point == -1) {
                edge_value_sums = -EXCEED;
                break;
            }
            has_add.add(min_point);
            other_point.remove(min_point);
            edge_value_sums += min;
        }
    }

    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            other_point.add(i);
        }
        m = sc.nextInt();
        for (int i = 0; i < g.length; i++) Arrays.fill(g[i], EXCEED);
        while (m-- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int w = sc.nextInt();
            g[a][b] = Math.min(g[a][b], w);
            g[b][a] = Math.min(g[b][a], w);
        }
        prim();
        if (edge_value_sums == -EXCEED) System.out.println("impossible");
        else System.out.println(edge_value_sums);
    }
}