题目描述

prime 最小生成树

JAVA 代码

//解题思路：
/*Prim算法求最小生成树的逻辑如下：
1.循环n次，代表向集合中添加n个节点
2.每一次选择距离集合最近的节点
在这里有一个判断就是如果此时还未加入集合中的所有点到集合的距离最小值为负无穷，则说明最小生成树不存在！
3.使用最新加入的这个节点去更新其它节点到集合的距离
*/

//时间复杂度分析：
//使用Prim求最小生成树的时间复杂度为O(n^2),n为节点的个数


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

class Main{

    static int N = 510, n,m, max = 0x3f3f3f3f;
    static int[][] g = new int[N][N];
    static int[] d = new int[N];
    static boolean[] st = new boolean[N];

    static int prime(){
        Arrays.fill(d, max);//初始化所有点到集合的距离都为正无穷
        int res = 0;//用于记录最小生成树的权值
        //循环n次
        for(int i = 0;i<n;i++){
            //找到距离集合最近的那个点
            int t = -1;
            for(int j=1;j<=n; j++){
                if((t==-1 || d[t]> d[j])&&!st[j]){
                    t = j;
                }
            }

            //如果此时不是寻找的第一个点，但是所有点到集合的距离最小值为正无穷，说明不存在最小生成
            if(i>0 && d[t] == max) return -1;
            if(i>0) res += d[t];
            st[t] = true;         

            //用新加进来的点去更新其它点到集合的距离
            for(int j =1;j<=n;j++){
                if(d[j] > g[t][j]) d[j] = g[t][j];
            }
        }
        return res;
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for(int i = 1;i<=n; i++){
            Arrays.fill(g[i], max);
        }

        while(m-->0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            g[a][b] = g[b][a] = Math.min(g[a][b], c);
        }

        int t = prime();
        if(t==-1)System.out.println("impossible");
        else System.out.println(t);

    }
}