题目信息

题目类型
练习
题目年份
2025
题目题型
编程题
关 键 词
求最小生成树的Prim算法

题目题干

求最小生成树的Prim算法

请编写程序,实现在带权的无向图中求最小生成树的 Prim 算法。uUN100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
注意:当多个待收录顶点到当前点集的距离等长时,按编号升序进行收录。uUN100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式:

输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点数 n(≤100)和边数 m。uUN100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
随后 m 行,每行给出一条无向边两端点的编号、权重。顶点编号从 0 开始,权重(≤100)为整数。同行数字均以一个空格分隔。uUN100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式:

参考样例。uUN100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
首先在一行中输出 total weight = x,其中 x 为最小生成树中所有边的总权重。如果最小生成树不存在,则 x 为 −1。uUN100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
随后在一行中按顶点编号升序输出每个顶点在最小生成树中的父结点的编号。为输出简单起见,每个数字后有一个空格。uUN100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
注意:此处默认顶点 0 为最小生成树的根结点,其父结点编号规定为 −1。算法初始化时,所有顶点(除了根结点)的父结点编号默认为 0。uUN100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入样例 1:

6 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1

输出样例 1:

total weight = 11
-1 0 0 1 5 2 

输入样例 2:

7 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1

输出样例 2:

total weight = -1
-1 0 0 1 5 2 0 

答案解析

相关题目

拓扑排序请编写程序,实现对有向无权图中的顶点进行拓扑排序的算法。 注意:如果拓扑序不唯一,输出任何一个序列都可以,由特殊裁判程序判定正确性。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要
求最小生成树的Prim算法请编写程序,实现在带权的无向图中求最小生成树的 Prim 算法。 注意:当多个待收录顶点到当前点集的距离等长时,按编号升序进行收录。 输入格式: 输入首先在第一行给出两个正
求所有点对间最短路的Floyd-Warshall算法请编写程序,实现在带权有向图中求所有点对间最短路的 Floyd-Warshall 算法。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要
求单源最短路的Bellman-Ford算法请编写程序,实现在带负值权的有向图中求单源最短路的 Bellman-Ford 算法。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点
求单源最短路的Dijkstra算法请编写程序,实现在带权的有向图中求单源最短路的 Dijkstra 算法。 注意:当多个待收录顶点路径等长时,按编号升序进行收录。 输入格式: 输入首先在第一行给出两
哥尼斯堡的“七桥问题” 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿及连接它们的七座桥,如下图所示。 可否走过这样的七座桥,而且每桥只走过一次?瑞士数学家欧拉(Leonhard Euler
哥尼斯堡的“七桥问题” 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿及连接它们的七座桥,如下图所示。 可否走过这样的七座桥,而且每桥只走过一次?瑞士数学家欧拉(Leonhard Euler
双连通分量本题请你编写程序,输出给定无向连通图中的割点和割边。 输入格式: 输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex(≤20)。 第二行给出两个正整数,依次为当前要创建的
欧拉回路本题请你编写程序,输出给定无向连通图中的欧拉回路。 输入格式: 输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex(≤20)。 第二行给出两个正整数,依次为当前要创建的图的
强连通分量本题请你编写程序,输出给定有向图中的各个强连通分量,并统计强连通分量的个数。 输入格式: 输入首先在第一行给出 2 个整数,依次为有向图的顶点数 n(0<n≤15)和边数 m。 随后

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢