AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 858. Prim算法求最小生成树    原题链接    简单

作者: 作者的头像   JAVA小老弟 ,  2020-08-08 15:49:45 ,  阅读 125


1



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
    static int[][] g;
    static int[] used=new int[100100];
    static int n;
    static int m;
    static int[] dis;
    public static void main(String[] args) throws IOException {
        BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
        String line[]=r.readLine().split(" ");
        n=Integer.valueOf(line[0]);
        m=Integer.valueOf(line[1]);

        g=new int[510][510];
        // 先用邻接表存储
        for (int i = 0; i <510 ; i++) {
            for (int j = 0; j <510 ; j++) {
                g[i][j]=0x3f3f3f;
            }
        }
        dis=new int[100100];
        for (int i = 0; i <m ; i++) {
            String line1[]=r.readLine().split(" ");
            int u=Integer.valueOf(line1[0]);
            int v=Integer.valueOf(line1[1]);
            int w=Integer.parseInt(line1[2]);
            // 将最小的进行存储
            g[u][v]=g[v][u]=Math.min(g[v][u],w);
        }

        int res=prim();
        if(res==0x3f3f3f)
            System.out.println("impossible");
        else
            System.out.println(res);
    }

    public static int prim(){
        int res=0;

        // 点到集合的距离定义为正无穷
        Arrays.fill(dis,0x3f3f3f);

        for (int i = 1; i <=n ; i++) {
            // 遍历从1-n  因为需要加入n个点
            int t=-1;// 标志一下是不是可以找到下一个更新的点
            //找到一个到集合距离是最短的点t 用t去更新到集合的距离
            for (int j = 1; j <=n ; j++) {
                if(used[j]==0 && (t==-1 || dis[t]>dis[j])) {
                    t = j;
                }
            }
            //如果这个点不存在的话 将第一次给排除出去 因为第一次总是特殊的
            if((i!=1 )&& (dis[t]==0x3f3f3f))
                return 0x3f3f3f;
            //当不是起点的时候 生成树权重++

            if(i!=1)
                res+=dis[t];
            //新加入了一个点 看看能不能更新距离 为下次寻找离集合最近的点做准备
            for (int j = 1; j <=n ; j++) {
                dis[j]=Math.min(dis[j],g[t][j]);
            }
            used[t]=1;
            System.out.println(t);
        }
        return res;
    }



}

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息