![]() 成都石室中学、福建长乐一中信奥教练联合呈现。题库教师群:515658966,仅供教师加入 |
初赛题库:提高组 普及组 拥有自我:一本通自由题库 更多拥有:扩展题库 编程启蒙 |
你现在还未登录哦! 用户登录 找回密码 注册新用户 |
---|
首页 | 排名 | 提交记录 | 题目列表 | 测试比赛 | 教师频道 | 正版书籍 | 关于 |
---|
1906:【18NOIP提高组】赛道修建时间限制: 1000 ms 内存限制: 524288 KB 提交数:941 通过数: 431 【题目描述】C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建 m 条赛道。 C 城一共有n 个路口,这些路口编号为 1,2,…,n,有n−1 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 i 条道路连接的两个路口编号为ai和bi,该道路的长度为li。借助这 n−1 条道路,从任何一个路口出发都能到达其他所有的路口。 一条赛道是一组互不相同的道路e1,e2,…,ek,满足可以从某个路口出发,依次经过道路e1,e2,…,ek(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。 目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的m条赛道中长度最小的赛道长度最大(即m条赛道中最短赛道的长度尽可能大)。 【输入】输入第一行包含两个由空格分隔的正整数n,m,分别表示路口数及需要修建的赛道数。 接下来n−1 行,第i 行包含三个正整数ai,bi,li,表示第i 条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这n−1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。 【输出】输出共一行,包含一个整数,表示长度最小的赛道长度的最大值。 【输入样例】7 1 1 2 10 1 3 5 2 4 9 2 5 8 3 6 6 3 7 7 【输出样例】31 【提示】【输入输出样例1说明】 所有路口及适合于修建赛道的道路如下图所示: 道路旁括号内的数字表示道路的编号,非括号内的数字表示道路长度。 需要修建 1 条赛道。可以修建经过第 3,1,2,6 条道路的赛道(从路口 4 到路口 7),则该赛道的长度为 9+10+5+7=31,为所有方案中的最大值。 【样例输入2】 9 3 1 2 6 2 3 3 3 4 5 4 5 10 6 2 4 7 2 9 8 4 7 9 4 4 【样例输出2】 15 【输入输出样例2说明】 所有路口及适合于修建赛道的道路如下图所示: 需要修建 3 条赛道。可以修建如下 3 条赛道: 1.经过第 1,6 条道路的赛道(从路口 1 到路口 7),长度为 6+9=15; 2.经过第 5,2,3,8 条道路的赛道(从路口 6 到路口 9),长度为 4+3+5+4=16; 3.经过第 7,4 条道路的赛道(从路口 8 到路口 5),长度为 7+10=17。长度最小的赛道长度为 15,为所有方案中的最大值。 【输入输出样例3】 样例数据3 【数据规模与约定】 所有测试数据的范围和特点如下表所示:
其中,“分支不超过3”的含义为:每个路口至多有3条道路与其相连。 对于所有的数据,2≤n≤50,000,1≤m≤n−1,1≤ai,bi≤n,1≤li≤10,000。 |
本题库与《信息学奥赛一本通(C++版)》(南京大学出版社)配套。 本网站属公益、非盈利性质,不涉及与书相关的商业活动,仅适当接受少量赞助以支持网站的运行维护。 蜀ICP备2024068936号-2 联系我们: 248801752@qq.com 23967609@qq.com | 网站使用规则 网站用户协议 |