我要招人

去企业版

首页 > 试题广场 >

最小生成树

[编程题]最小生成树

热度指数：18895 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个有 n 户人家的村庄，有 m 条路相互连接着。村里现在要修路，每条路都有一个成本价格，现在请你帮忙计算下，最少需要花费多少钱，就能让这 n 户人家连接起来。

$cost$ 为一个二维数组，每个元素是一个长度为 3 的一维数组 $a$ ， $a[0]$ 和 $a[1]$ 表示村庄 $a[0]$ 和村庄 $a[1]$ 有一条路，修这条路的成本价格为 $a[2]$ 。

每户之间可能有多条道路连接，但不可能自己与自己相连。

数据范围: $1 \le n \le 5 \times 10^3$ ， $1 \le m \le 5 \times 10^5$ ， $1 \le a[2] \le 10^4$

进阶：时间复杂度 $O(n+mlogm)$ ，空间复杂度 $O(n)$

示例1

输入

3,3,[[1,3,3],[1,2,1],[2,3,1]]

输出

示例2

输入

2,1,[[1,2,1]]

输出

算法知识视频讲解

摸鱼学大师

发表于 2021-12-09 21:11:17

题目的主要信息： n个节点，m条边，边权记录在邻接表cost中求最小生成树的总边权方法一：kruskal算法+并查集具体做法：最小生成树，我们可以连通的点看成是同一个并查集，利用并查集的思想来逐渐加边使所有节点连在一起。同时，最小生成树需要用kruskal算法的贪心思想，先对邻接表按照边展开全文

牛一霸

发表于 2021-07-29 22:01:23

题目：最小生成树描述：一个有n户人家的村庄，有m条路连接着。村里现在要修路，每条路都有一个代价，现在请你帮忙计算下，最少需要花费多少的代价，就能让这n户人家连接起来。示例1：输入：3,3,[[1,3,3],[1,2,1],[2,3,1]]，返回值：2 解法一：思路分析：通过观察这道题，有n户人家，需展开全文

Ruoji55555

发表于 2021-03-14 11:38:10

Kruskal裸题直接套模板（本来想再写一个Prim.... 太难了） public int miniSpanningTree (int n, int m, int[][] cost) { // write code here int[] father 展开全文

fred-coder

发表于 2022-01-14 13:54:41

最小生成树算法 Kruskal,对所有边按照权重排序,利用并查集确定连通性,最终得出最小生成树的值 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 返回最小的花费代价使得这n户人家连接起来 # @param n int整型 n户人家的村庄 # @param 展开全文

Peterliang

发表于 2021-11-22 23:26:50

NC159 题解 | #最小生成树# 题意分析给出一张图，图上有n个节点，m条路，现在，我们需要计算将所有的点构成一个连通图所需要的最小的代价，题目会给出某两个结点之间的成本，需要我们最小化总的成本。思路分析我们首先很明确的知道这个就是需要我们求出图上的一棵最小生成树。我们发现，我们可以展开全文

LourisXu

发表于 2021-08-24 22:32:18

Prim 采用邻接矩阵，方便判重； class Solution { public: const int inf = 0x3f3f3f3f; struct Node{ int v; int c; Node(int _v, int _c) 展开全文

youxiwang

发表于 2022-04-01 14:58:43

Prim和Kruskal两种方法 // Prim // Time: O(MlogM), each edge is inserted to minHeap once. // Spcae: O(n) import java.util.*; public class Solution { pu 展开全文

琼洁

发表于 2024-10-26 14:44:54

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 返回最小的花费代价使得这n户人家连接起来 # @param n int整型 n户人家的村庄 # @param m int整型 m条路 # @param cost int整型二维数组一维3个参数，表示连接1个村展开全文