首页 > 其他分享 >最小生成树

最小生成树

时间:2023-05-18 20:35:51浏览次数:39  
标签:le java int 最小 生成 static import new

最小生成树

题目描述

如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz

输入格式

第一行包含两个整数 \(N,M\),表示该图共有 \(N\) 个结点和 \(M\) 条无向边。

接下来 \(M\) 行每行包含三个整数 \(X_i,Y_i,Z_i\),表示有一条长度为 \(Z_i\) 的无向边连接结点 \(X_i,Y_i\)。

输出格式

如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz

样例 #1

样例输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

样例输出 #1

7

提示

数据规模:

对于 \(20\%\) 的数据,\(N\le 5\),\(M\le 20\)。

对于 \(40\%\) 的数据,\(N\le 50\),\(M\le 2500\)。

对于 \(70\%\) 的数据,\(N\le 500\),\(M\le 10^4\)。

对于 \(100\%\) 的数据:\(1\le N\le 5000\),\(1\le M\le 2\times 10^5\),\(1\le Z_i \le 10^4\)。

样例解释:

所以最小生成树的总边权为 \(2+2+3=7\)。

朴素Prim

dist[i] = INF
for(int i = 0; i < n; i++)
	1.找到集合外距离最近的点  t
	2.用t更新其他点到集合的距离
	3.st[t] = true

代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    static final int N = 5010, INF = 0x3f3f3f;
    static int n, m;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static List<int[]>[] g = new List[N];
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        n = nextInt();
        m = nextInt();
        int x, y, z;
        Arrays.setAll(g, a -> new ArrayList<>());
        for (int i = 0; i < m; i++) {
            x = nextInt();
            y = nextInt();
            z = nextInt();
            g[x].add(new int[]{y, z});
            g[y].add(new int[]{x, z});
        }
        Arrays.fill(dist, INF);
        int res = prim();
        if (res == -1) System.out.println("orz");
        else System.out.println(res);
    }

    public static int prim() {
        int res = 0;
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            if (i > 0 && dist[t] == INF) return -1;
            if (i > 0) res += dist[t];
            st[t] = true;
            for (int[] nei : g[t]) {
                int x = nei[0], w = nei[1];
                dist[x] = Math.min(dist[x], w);
            }
        }
        return res;
    }

    public static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
}

Kruskal算法

1.所有边按权重从小到大排序 O(mlogm)
2.枚举每条边a,b 权重c
    if(a,b不连通)
        将这条边加入集合中

标签:le,java,int,最小,生成,static,import,new
From: https://www.cnblogs.com/tobuv/p/17413205.html

相关文章

  • 打卡 c语言趣味编程 求最小公倍数
    问题描述:求任意两个正整数的最小公倍数(LCM)。思路:输入两个正整数,假设为num1和num2。定义一个变量lcm并初始化为较大的那个数(即lcm=max(num1,num2))。进入一个循环,循环条件为lcm不能同时被num1和num2整除。在每次循环中,将lcm增加1。循环结束后,lcm的值就是最小......
  • Postman+Newman生成HTML接口测试报告
    NewMan是官方提供的专门用于posman进行自动化的命令行工具环境配置:Node.js:Newman是基于Node.js,所以安装NewMan之前需要保证本地有安装Node.jsNewMan:npminewman-g,安装成功后输入newman-v来检查版本,显示出版本即表示安装成功html格式报告的插件:npminstall-gnewman......
  • Oracle数据库生成AWR日报的方法
    1.打开pl/sql命令行2.打开awrrpt.sql文件 3.选择文件类型4.输入天数 5.选择开始时间 6.选择结束时间7.输入日报名字,一般为了方便,我输入的是月份日期 8.打开awr日报所在位置,并修改格式为html  ......
  • 一张图解析FastAdmin中的FormBuilder表单生成器
     功能描述在使用FastAdmin一键生成CRUD后,默认的生成的都是原生HTML的组件代码,会有许多不熟悉前端的小伙伴改动起来会比较费劲。其实在FastAdmin中有一个简单的FormBuilder,但是它只能生成一些简单的文本框或下拉框,像FastAdmin中常用的动态下拉框、城市选择框、联动框,它就没法实......
  • Midjourney|文心一格prompt教程[Text Prompt(下篇)]:游戏、实物、人物、风景、动漫、邮票
    Midjourney|文心一格prompt教程[TextPrompt(下篇)]:游戏、实物、人物、风景、动漫、邮票、海报等生成,终极模板教学场景6:游戏Prompt真的越长越好吗?按照Midjourney的官方文档里的说法,并不一定:Promptscanbeverysimple.Singlewords(orevenanemoji!)willproducean......
  • 通过1分钟生成其它线的bar配置文件
    import jsonfrom datetime import datetime, timedeltaimport math# 获取开始时间和结束时间start_time = datetime.strptime("00:00:00", "%H:%M:%S")end_time = datetime.strptime("23:59:00", "%H:%M:%S")# 创建字典,以时间字符串为键,值为所属时间段的开......
  • 微信生成常用接口地址枚举类
    /***@description:微信接口地址枚举*@author:Mr.Fang*@create:2023-05-18**/publicenumWxEnum{BASIC_URL("小程序与公众号","https://api.weixin.qq.com",""),MCH_BASIC_URL("微信商户","https://api.mch.weixin......
  • Oracel反向生成PDM后没有字段说明
    从name替换commentOptionExplicitValidationMode=TrueInteractiveMode=im_BatchDimmdl'thecurrentmodel'getthecurrentactivemodelSetmdl=ActiveModelIf(mdlIsNothing......
  • 最小生成树
    最小生成树最小生成树(MinimumSpanningTree,简称MST)是连接所有节点的边的集合中,权值最小的连通子图的边集合,即一个加权连通图中,找到一棵生成树,使得所有边的权值之和最小。最小生成树的求解算法主要有两种:Kruskal算法Kruskal算法也是一种贪心算法,将所有边按照权值`从小到大......
  • 最小公倍数
    一问题描述输入两个数求出他们的最小公倍数。二设计思路从一开始查看这两个数是否是因子,将最小的数输出。三程序流程图 四伪代码实现#include<iostream>usingnamespacestd;intmain(){ intm,n; for(intj=0;j<2;j++){ cin>>m; cin>>n; for(inti=1;i<=m*n;i++){ if(i......