鱼C论坛

 找回密码
 立即注册
查看: 300|回复: 3

CCF题 城市规划

[复制链接]
最佳答案
0 
发表于 2019-11-14 22:59:35 | 显示全部楼层 |阅读模式
50鱼币
本帖最后由 为之不止 于 2019-11-17 23:37 编辑

如题:
                                                                                                        城市规划(tree)
【题目描述】 有一座城市,城市中有 N 个公交站,公交站之间通过 N-1 条道路连接,每条道 路有相应的长度。保证所有公交站两两之间能够通过一唯一的通路互相达到。 两个公交站之间路径长度定义为两个公交站之间路径上所有边的边权和。 现在要对城市进行规划,将其中 M 个公交站定为“重要的”。 现在想从中选出 K 个节点,使得这 K 个公交站两两之间路径长度总和最小。输出 路径长度总和即可(节点编号从 1 开始)。
【输入格式】
从标准输入读入数据。 第 1 行包含三个正整数 N,M 和 K 分别表示树的节点数,重要的节点数,需要选出的节点数。 第 2 行包含 M 个正整数,表示 M 个重要的节点的节点编号。 接下来 N-1 行,每行包含三个正整数 a,b,c,表示编号为 a 的节点与编号为 b 的节点之间有一条权值为 c 的无向边。每行中相邻两个数之间用一个空格分隔。
【输出格式】
输出到标准输出。 输出只有一行,包含一个整数表示路径长度总和的最小值。
【样例输入】
5 3 2
1 3 5
1 2 4
1 3 5
1 4 3
4 5 1
【样例输出】
4

本人思考两天了,还是想不出来。
特来求问这道题应该用什么算法?求C语言解决方法


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
60 
发表于 2019-11-14 23:56:01 | 显示全部楼层
文本中好像有些东西复制过来后变成乱码了,你看看是编辑一下还是咋的?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
 楼主| 发表于 2019-11-15 00:08:05 | 显示全部楼层
阴阳神万物主 发表于 2019-11-14 23:56
文本中好像有些东西复制过来后变成乱码了,你看看是编辑一下还是咋的?

好的,我这就去改,多谢提醒
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-12-5 13:29:29 From FishC Mobile | 显示全部楼层
我也不会,能帮我一下吗,拜托了
明天就要验收了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2020-1-22 06:36

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表