#P2020124. 食材运输

    ID: 134 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 入门 上传者: 标签>入门赛制:OI来源:wyfoj http://127.0.0.1贪心

食材运输

食材运输

题目描述

题目背景

在T市有很多个酒店,这些酒店对于不同种类的食材有不同的需求情况,莱莱公司负责每天给这些酒店运输食材。

由于酒店众多,如何规划运输路线成为了一个非常重要的问题。你作为莱莱公司的顾问,请帮他们解决这个棘手的问题。

题目描述

T市有N个酒店,这些酒店由N−1条双向道路连接,所有酒店和道路构成一颗树。不同的道路可能有不同的长度,运输车通过该道路所需要的时间受道路的长度影响。

在T市,一共有K种主流食材。莱莱公司有K辆车,每辆车负责一种食材的配送,不存在多辆车配送相同的食材。

由于不同酒店的特点不同,因此不同酒店对食材的需求情况也不同,比如可能1号酒店只需要第1,5种食材,2号酒店需要全部的K种食材。

莱莱公司每天给这些公司运输食材。对于运输第i种食材的车辆,这辆车可以从任意酒店出发,然后将食材运输到所有需要第i种食材的酒店。假设运输过程中食材的装卸不花时间,运输车足够大使得其能够在出发时就装满全部所需食材,并且食材的重量不影响运输车的速度。

为了提高配送效率,这K辆车可以从不同的酒店出发。但是由于T市对于食品安全特别重视,因此每辆车在配送之前需要进行食品安全检查。鉴于进行食品安全检查的人手不足,最多可以设置M个检查点。

现在莱莱公司需要你制定一个运输方案:选定不超过M个酒店设立食品安全检查点,确定每辆运输车从哪个检查点出发,规划每辆运输车的路线。

假设所有的食材运输车在进行了食品安全检查之后同时出发,请制定一个运输方案,使得所有酒店的等待时间的最大值最小。酒店的等待时间从运输车辆出发时开始计算,到该酒店所有需要的食材都运输完毕截至。如果一个酒店不需要任何食材,那么它的等待时间为0。

输入格式

从标准输入读入数据。

输入的第一行包含3个正整数N,M,K(1≤N≤10^2,1≤M≤K≤10),含义见题目描述。

接下来N行,每行包含K个整数。每行输入描述对应酒店对每种食材的需求情况,1表示需要对应的食材,0表示不需要。

接下来N−1行,每行包含3个整数u,v,w,表示存在一条通行时间为w的双向道路连接u号酒店和v号酒店。保证输入数据是一颗树,酒店从1编号到N,保证1≤u,v≤N并且1≤w≤10^6。

输出格式

输出到标准输出。

输出一个整数,表示在你的方案中,所有酒店的等待时间的最大值。

数据范围

(原站未提供,导入后需人工补齐)

样例

6 1 2
1 0
0 0
1 0
0 1
0 1
0 1
1 2 7
2 3 2
2 4 4
4 5 5
4 6 3
15
6 2 2
1 0
0 0
1 0
0 1
0 1
0 1
1 2 7
2 3 2
2 4 4
4 5 5
4 6 3
9

提示

样例1解释

![D1.png](file://be98e782bd.png)

样例1的输入数据如上图。由于限制了最多只能设置1个检查点,因此可以设置两辆运输车的路径如下:

![D2.png](file://901a6b2021.png)

在2号酒店设置检查点,最晚拿到所有食材的酒店为3号酒店,等待时间为9。

样例2解释

样例2的输入数据和样例1几乎完全相同,唯一的区别在于样例2中允许最多设置2个检查点。我们可以设置两辆运输车的路径如下:

![D3.png](file://5311482119.png)

在1号酒店和6号酒店设置检查点,最晚拿到所有食材的酒店为5号酒店,等待时间为15。

子任务

本题目数据规模如下

![D4.png](file://874cdd9e38.png)