食品從業人員試題答案2021，CCF202012-4 食材運輸（100分題解鏈接）

試題編號： 202012-4
試題名稱： 食材運輸
時間限制： 1.0s
內存限制： 512.0MB
問題描述：

題目背景

食品從業人員試題答案2021？在T市有很多個酒店，這些酒店對于不同種類的食材有不同的需求情況，萊萊公司負責每天給這些酒店運輸食材。

由于酒店眾多，如何規劃運輸路線成為了一個非常重要的問題。你作為萊萊公司的顧問，請幫他們解決這個棘手的問題。

題目描述

2021年餐飲從業考試卷及答案，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²,1≤M≤K≤10)，含義見題目描述。

接下來N行，每行包含K個整數。每行輸入描述對應酒店對每種食材的需求情況，1表示需要對應的食材，0表示不需要。

接下來N-1行，每行包含3個整數u,v,w，表示存在一條通行時間為w的雙向道路連接u號酒店和v號酒店。保證輸入數據是一顆樹，酒店從1編號到N，保證1≤M≤K并且1≤w≤10⁶。

輸出格式

輸出到標準輸出。

輸出一個整數，表示在你的方案中，所有酒店的等待時間的最大值。

樣例1輸入

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

樣例1輸出

15

樣例1解釋

樣例1的輸入數據如上圖。由于限制了最多只能設置1個檢查點，因此可以設置兩輛運輸車的路徑如下：

在2號酒店設置檢查點，最晚拿到所有食材的酒店為3號酒店，等待時間為9。

樣例2輸入

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

樣例2輸出

9

樣例2解釋

樣例2的輸入數據和樣例1幾乎完全相同，唯一的區別在于樣例2中允許最多設置2個檢查點。我們可以設置兩輛運輸車的路徑如下：

在1號酒店和6號酒店設置檢查點，最晚拿到所有食材的酒店為5號酒店，等待時間為15。

子任務

本題目數據規模如下：

問題鏈接：CCF202012-4 食材運輸
問題簡述：（略）
問題分析：參考鏈接是100分。
程序說明：（略）
參考鏈接：
第 21 次 CCF CSP 認證 第 4 題 食材運輸 題解
202012-4 食材運輸
CSP202012-4 食材運輸（圖論+狀壓DP）
CSP202012-4 食材運輸 樹狀DP+狀壓DP
題記：（略）

100分的C++語言程序如下：