Problem 2084 --算法7-9：最小生成树

2084: 算法7-9：最小生成树

上一题 正确率: $136.45\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $502$ 正确数量 $685$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 图论 最小生成树

Description

最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。
可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。
而在常用的最小生成树构造算法中，普里姆（Prim）算法是一种非常常用的算法。以下是其算法的大致结构：

在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。

Input

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。

Output

只有一个整数，即最小生成树的总代价。请注意行尾输出换行。

Sample Input复制

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

Sample Output复制

6

提示

在本题中，需要掌握图的深度优先遍历的方法，并需要掌握无向图的连通性问题的本质。通过求出无向图的连通分量和对应的生成树，应该能够对图的连通性建立更加直观和清晰的概念。


推荐代码 查看2084 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$0 $ms] Rock.Lee 866107 2022-06-16 14:23:12
内存最少[$0 $KB] 557744 580898 2020-04-30 14:13:25
第一AC 范晋豪@信息与计算科学142 152730 2017-11-16 15:10:16
第一挑战 范晋豪@信息与计算科学142 152730 2017-11-16 15:10:16

赛题来源/所属竞赛 数据结构高分笔记 数据结构高分笔记

竞赛编号 竞赛名称 竞赛时间 访问比赛
1803 2023-2024-2学期<计算机专业竞赛实训> 第7-8周练习：图论算法【22计算机】 2024-04-08 00:00:00 请登录
1771 2023-2024-1学期<编译原理> 第15-17周练习：图算法、中间代码生成优化实验【21计算机1234】 2023-12-11 09:00:00 请登录
1743 2022-2023-2学期<计算机专业竞赛实训> 第9-10周练习：图论算法【21计算机12345】 2023-04-17 00:00:00 请登录
1689 2021-2022-2学期<算法分析与设计> 第9-10周练习：图论算法 2022-04-18 08:00:00 请登录
1615 2020-2021-2学期<算法分析与设计> 第14-15周练习：图论算法 2021-05-17 00:00:00 请登录