图论：最小生成树prim算法

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

       Scanner in =new Scanner(System.in);
       int  n= in.nextInt();
       int  m=in.nextInt();
        //初始化图为最大数字
        int[][] grid=new int[n+1][n+1];
        for (int i = 0; i <=n ; i++) {
            Arrays.fill(grid[i],Integer.MAX_VALUE);
        }

        for (int i = 0; i < m; i++) {
            int s=in.nextInt();
            int t=in.nextInt();
            int v=in.nextInt();
            //如果有重边,需要取最小,即输入数据可能为:
            // 2 4 44
            // 4 2 206
            // 后面的206会覆盖掉前面的44导致答案错误,需要取最小
            grid[s][t]=grid[t][s]=Math.min(v,grid[t][s]);
        }

        int []mindist=new int[n+1];
        Arrays.fill(mindist,Integer.MAX_VALUE);
//从节点1开始
        mindist[1]=0;

        boolean []isInTree=new boolean[n+1];

        //找n-1条边
        for (int i =1; i < n; i++) {
            int minVal=Integer.MAX_VALUE;
            int cur=-1;
            //找到最小的权值,获取最小权值和他的索引
            for (int j=1;j<=n;j++){
                if (!isInTree[j]&&mindist[j]<minVal){
                    minVal=mindist[j];
                    cur=j;
                }
            }
            //如果除了第一步之外,选到的最小值仍然是max,说明图不联通
            if (cur==-1){//后面的判断条件可以不写,是等价的||minVal==Integer.MAX_VALUE
                System.out.println("不成环");
                return;
            }

            //加入生成树
            isInTree[cur]=true;
            //更新所有非生成树节点到树的距离
            for (int j = 1; j <= n; j++) {
                if (!isInTree[j]&&grid[cur][j]<mindist[j]){
                    mindist[j]=grid[cur][j];
                }
            }
        }

        //获取结果
        int result=0;
        for (int i = 2; i <=n ; i++) {
            result+=mindist[i];
        }
        System.out.println(result);
       in.close();

    }

}