成都石室中学、福建长乐一中信奥教练联合呈现。题库教师群:515658966,仅供教师加入
初赛题库:提高组 普及组

拥有自我:一本通自由题库

更多拥有:扩展题库  编程启蒙
你现在还未登录哦!
用户登录  找回密码
注册新用户

1906:【18NOIP提高组】赛道修建


时间限制: 1000 ms         内存限制: 524288 KB
提交数:941    通过数: 431

【题目描述】

C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建 m 条赛道。

C 城一共有n 个路口,这些路口编号为 1,2,,n,有n1 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 i 条道路连接的两个路口编号为aibi,该道路的长度为li。借助这 n1 条道路,从任何一个路口出发都能到达其他所有的路口。

一条赛道是一组互不相同的道路e1,e2,,ek,满足可以从某个路口出发,依次经过道路e1,e2,,ek(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。

目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的m条赛道中长度最小的赛道长度最大(即m条赛道中最短赛道的长度尽可能大)。

【输入】

输入第一行包含两个由空格分隔的正整数n,m,分别表示路口数及需要修建的赛道数。

接下来n1 行,第i 行包含三个正整数ai,bi,li,表示第i 条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这n1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。

【输出】

输出共一行,包含一个整数,表示长度最小的赛道长度的最大值。

【输入样例】

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

【数据规模与约定】

所有测试数据的范围和特点如下表所示:

测试点编号nmai=1bi=ai+1分支不超过3
15=1
210n1
315
41000=1
530,000
6
7n1
850,000
91,000
1030,000
1150,000
1250
13
14200
15
161000
17
1830,000
19
2050,000

其中,“分支不超过3”的含义为:每个路口至多有3条道路与其相连。

对于所有的数据,2n50,000,1mn1,1ai,bin,1li10,000

提交 统计信息


本题库与《信息学奥赛一本通(C++版)》(南京大学出版社)配套。
本网站属公益、非盈利性质,不涉及与书相关的商业活动,仅适当接受少量赞助以支持网站的运行维护。
蜀ICP备2024068936号-2  联系我们: 248801752@qq.com  23967609@qq.com
    网站使用规则
网站用户协议