e032: 7. 不回家的銷售員
標籤 :
通過比率 : 1人/4人 ( 25% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-01-23 16:55

內容

在派桑地區有N個城市,當地交通建設的成本很高,所以只有N - 1條道路,已知每條道路連接兩個不同的城市,而且任何兩個城市之間都還是有道路可以直接或間接到達。爪哇公司有K位銷售員,每位銷售員必須走訪若干個城市去執行他的任務,因為這是一個周期性的工作而且爪哇公司在每一個城市都有宿舍,所以每一位銷售員可以從任何一個城市開始,而完成他的拜訪任務後也不必回到起點。為了節省旅行成本,爪哇公司委託丙正正程式設計公司來幫忙規劃每一位銷售員的行程,身為丙正正公司的程式設計師,你的任務是要計算出所有銷售員所走的最小路程總和是多少。請注意每個銷售員所需拜訪的城市可能有重複,但是他們的任務是彼此獨立而無關的。



上圖展示一個範例,其中圖(a)顯示了8個城市與7條道路的資訊。假設K=2,也就是有兩位銷售員,而S1={3,5}以及S2={7,2,1,5,6}分別代表第一位與第二位銷售員需要拜訪的城市集合。圖(b)與(c)分別是這兩位銷售員必須走過的道路與城市,我們可以發現,第一位銷售員所需走的最短路程是從3走到5(或是5走到3),其長度是6,也就所經過的道路長總和;而第二位銷售員的最短路徑則是6->1->5->1->0->7->0->2,其長度是16。所以這個範例的最短總路程是6+16=22。此範例即為下面的範例1。

輸入說明

測試資料的第一行是兩個整數N與K,2 ≤ N ≤ 100,000,1 ≤ K ≤ N,分別代表城市與銷售員的數量,每個城市都以一個0 ~ N-1的整數來編號。接下來N-1行是道路資訊,每一行有三個整數a、b與w,代表一條道路連接城市a與b,而其長度為w,其中0≤ a, b < N且w是不超過1000的正整數。在道路資訊後接著的是每個銷售員需要拜訪的城市,以下第i行是第i位銷售員需要拜訪的城市集合Si,該行的第一個數字是該集合的城市數量 |Si|,接著是|Si|個城市編號。我們假設所有銷售員所需拜訪的城市數量總和$\color{black}{\sum_{i=1}^{N-1}{|S_i|} \le 2N}$。輸入資料同一行的數字間皆以空白隔開。

輸出說明

輸出所有銷售員所需要經過的最短路程總和。請注意答案可能超過232,但不會超過260

範例輸入
範例輸入 1:
8 2
6 1 4
1 4 1
1 5 1
1 0 3
0 2 5
3 0 2
0 7 1
2 3 5
5 7 2 1 5 6

範例輸入 2:
5 3
0 1 3
1 2 1
3 2 5
4 3 2
3 1 2 3
3 0 4 2
4 3 2 1 4
範例輸出
範例輸出 1:
22

範例輸出 2:
25
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (13%): 0.8s , <1M
公開 測資點#1 (1%): 0.8s , <1M
公開 測資點#2 (1%): 0.8s , <1M
公開 測資點#3 (1%): 0.8s , <1M
公開 測資點#4 (1%): 0.8s , <1M
公開 測資點#5 (7%): 0.8s , <10M
公開 測資點#6 (1%): 0.8s , <10M
公開 測資點#7 (1%): 0.8s , <10M
公開 測資點#8 (1%): 0.8s , <10M
公開 測資點#9 (1%): 0.8s , <10M
公開 測資點#10 (6%): 0.8s , <10M
公開 測資點#11 (1%): 0.8s , <10M
公開 測資點#12 (1%): 0.8s , <10M
公開 測資點#13 (1%): 0.8s , <10M
公開 測資點#14 (1%): 0.8s , <10M
公開 測資點#15 (58%): 0.8s , <10M
公開 測資點#16 (1%): 0.8s , <10M
公開 測資點#17 (1%): 0.8s , <10M
公開 測資點#18 (1%): 0.8s , <10M
公開 測資點#19 (1%): 0.8s , <10M
提示 :

本題共有四個子題,每一子題可有多筆測試資料:

第一子題,N ≤ 100,解出可以獲得 17 分;

第二子題,| Si | = 2,對每一個1 ≤ i ≤ K。解出可以獲得 11 分;

第三子題,| Si | = 4,對每一個1 ≤ i ≤ K。解出可以獲得 10 分;

第四子題,無額外限制。解出可以獲得 62 分。

標籤:
出處:
107學年度全國資訊學科能力競賽 [編輯:
icube (輸光光)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」