题库
题目列表
题单列表
题目收藏
记录
比赛
公开的比赛
我参与的比赛
用户
用户排名
近期排名
外部排名
用户对比
用户组列表
博客
集训队
赛事新闻
赛事列表
获奖情况
视频列表
登录
⭐关于举办浙江师范大学第23届大学生程序设计竞赛的通知
实验10 建立互联网络（最小生成树Prim算法）
1 Sec
64 MB
|
Markdown
显示标签
简单
(*1000)
DataStruct课程题库
598
1084
通过
提交
题目描述
农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。
输入格式
第一行包含一个整数 $N$ $(3 \le N \le 100)$，表示农场的个数。 第 $2$ 行至第 $N+1$ 行包含一个 $N \times N$ 的矩阵，矩阵内第 $i$ 行第 $j$ 个元素表示第 $i$ 个农场与第 $j$ 个农场之间的距离。 数据保证矩阵对角线上均为 $0$，且距离为不超过 $100000$ 的正整数。
输出格式
输出连接到每个农场的光纤的最小长度。
样例输入 #1
复制
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
样例输出 #1
复制
28
题面
提交
记录
统计
上一题
下一题
上传者
coach
创建时间
2013-11-28 17:40
修改时间
2024-02-12 18:03
Markdown 题面
×
登录
×
账号
密码
记住我