1236 - Disjoint Paths

給一張圖，具有 N 個點和 N-1 條有權重的邊。找到最多 K 條不相交(點和邊皆不重複使用)的路徑，而所有被選上的邊權重總和最大。

如上如所示，兩個不同限制下，在相同的圖中會有不同的答案。

在不相交路徑最多 K 條時，當 K = 1，如左圖所示，答案最大為 13 (5+2+6)。

當 K = 2，如右圖所示，答案最大為 15 ((5+1)+(3+6))。

Input 

輸入第一行會有一個整數 T，表示接下來的測資組樹。

對於每組測資，第一行會有兩個整數 N, K (K <= N <= 60)。

接下來會有 N - 1 行，每行上會有三個整數 A, B, D，表示一條無向邊於 A 到 B 權重為 D。
(1 <= A, B <= N, |D| <= 10000)

Output 

對於每組測資，輸出最大總和。

Sample Input 

2 
6 1 
1 2 5
3 2 2
3 4 6
6 3 3
2 5 1
6 2 
1 2 5
3 2 2
3 4 6
6 3 3
2 5 1

Sample Output 

13 
15

1199 - Elevator Stopping Plan

在 ZSoft Corp 這家公司中，每名員工都相當地勤奮，但是電梯問題總是困擾他們。
因為這家公司只有一台電梯運作，使得在早上的時候，總是會花很多時間在等待電梯。

Hal 相當聰明，想要改善這種情況，目標要把電梯改為更有效率，但這並不是簡單的工作。

公司總共有 31 樓，電梯上升一樓消耗 4 秒，也就是說將會使用 (31 - 1) ×4 = 120 秒到達頂樓，如果電梯打算停留某一層時，將會額外消耗 10 秒時間停止。如果電梯每層都停，將會消耗 30×4 + 29×10 = 410 秒 (不考慮停留在 31 樓)。

員工們可以打算爬樓梯，不管是往上或往下爬一層，都是消耗 20 秒。如果從 1 樓爬到 31 樓，則消耗 30×20 = 600 秒。當然，只爬樓梯肯定不是最好的方式。因此一些員工會使用電梯到達某一層之後，再爬樓梯到達他們自己的辦公室。

經過一段時間精密的思考後，Hal 最後找到一個方法改善這種情況。首先，電梯會先問所有人要到達的樓層，將會設計停留哪一層的方案，最小化最後一個人到達的時間。

例如，電梯被要求停留在第 4, 5, 10 樓時，停留方案為
1. 先停留於第 4 樓，此時消耗 3×4 = 12 秒，並且停止 10 秒。
2. 之後直接抵達 10 樓，此時時間為 3×4 + 10 + 6×4 = 46 秒。

到抵達 4 樓人在 12 秒時可以到達，抵達 5 樓的人可以在 12 + 20 = 32 秒，而要抵達 10 樓的人將在 46 秒後到達。


寫程式計算最小化最後一個人抵達的時間，並且輸出停留方案。

Input 

輸入有多組測資。

每組測資的格式如下：

n f₁ f₂ ... f_n

將會有 n 個樓層被要求停留， f₁ f₂ ... f_n 表示為要求停止的樓層。
 (n <= 30, 2 <= f₁ < f₂ < ... < f_n <= 31)

Output 

對於每組測資，輸出一行最小的最後一個人抵達的時間。

第二行，先輸出停留樓層的個數，再分別輸出停留樓層的編號。

如果有多組輸出，任何一組都可以。

Sample Input 

3 4 5 10
1 2
0

Sample Output 

46
2 4 10
4
1 2

1148 - The mysterious X network

École 理工學院已經存在深根柢固的同儕網路。

當同學遇到任何困難時，他可以藉由這個網路尋求協助，也就是說，他想要在網路上找到另一個人尋求協助，他必須由中間人代為轉達。

特別注意：同儕關係都是對稱的，而且必然可以找到所有人。

寫一個程式計算最少的中間人個數。

Input

輸入第一行有一個整數，表示有多少測資組。

對於每組測資，第一行會有一個整數 N (1 <= N <= 10⁵)，同儕編號為 0 到 N-1。

接下來會有 N 行，每行前 2 個整數 c, n_c ( <= 100) 表示同儕編號，以及關係個數。

接下來會有 n_c 個整數緊接在後，表示 c 的同儕。

最後一行會有兩個整數 c₁ 和 c₂ ，表示 c₁向 c₂ 求助。

Output

對於每組測資，分別輸出  c₁, c₂, 和最少中間人個數。

Sample Input 

1

4
0 3 1 2 3
1 1 0
2 2 0 3
3 2 0 2
1 2

Sample Output 

1 2 1

388 - Galactic Import

隨著新系統的引進，星系之間的出口進口貿易變得更加容易，HyperCommodities 打算進口物品從不同的星系，每個星系中的行星的原物料都有不同的價值。

• 每個星系中最多有 26 個星球，每個星球編號從 'A' 到 'Z'。
• 每個星球都可以進口和出口，而且都有不同的原物料。
• 其中會存在兩個星球間有貿易路線，每當原物料由其他星球轉口出去，每轉一次原物料價值將會折損當下的 5%。
• 至少存在一個星球會向地球開放貿易。

找到其中一個星球的原物料進口到地球具有最高價值。

Input

輸入有多組測資。

每組測資第一行會有一個整數 N 表示描述星球間的關係。

每一行的格式如下：

1. 星球的英文字母代號
2. 空白
3. 原物料的價值 d.dd
4. 空白
5. 一組字串，表示可以出口到的地方。以 '*' 表示地球。

Output

對於每組測資，輸出 ``Import from P''，P 為最高價值的星球代號。如果有多個，則選擇字典順序最小的。

Sample Input

1
F 0.81 *
5
E 0.01 *A
D 0.01 A*
C 0.01 *A
A 1.00 EDCB
B 0.01 A*
10
S 2.23 Q*
A 9.76 C
K 5.88 MI
E 7.54 GC
M 5.01 OK
G 7.43 IE
I 6.09 KG
C 8.42 EA
O 4.55 QM
Q 3.21 SO

Sample Output

Import from F
Import from A
Import from A

11487 - Gathering Food

冬天來臨，天氣越來越冷，許多動物採取不同的方法來適應冬天。

- 遷徙，移動到溫暖的地方。

- 很少有動物仍在冬天保持活躍。

- 冬眠，動物藉由深沉睡眠，降低體溫、心跳速度，而在秋天時準備足夠的食物以及體內脂肪。

而這題著重於第三點的例子，觀察一種特別的熊。


這種熊在一個特別的森林，將這個森林定義為 N x N 的網狀格子，每個格子只會有下列三種資訊。


'.' 空地
'#' 障礙物
[A-Z] 英文字母

森林中至少存在一個英文字母，所有字母只會存在唯一一個，如果存在有 n 個字母，這必然只會存在前 n 個字母，即當 n = 3 時，確切只會有 1 A, 1 B, 1 C。

這些字母表示當地區的食物，熊會從 'A' 開始搜集其他食物，每次只會往四個方向(上下左右)移動，由於特別的習性，會根據字母順序搜集食物，當熊到達食物所在地時，才能將食物收集起來。

計算熊收集食物的最少移動步數，以及在最少移動步數下，有多少移動方法。


// 翻譯備註，非要撿起的食物必須當做障礙物。

Input

有多組測資，每組第一行有一個整數 N (N <= 10)。

Output

對於每組測資，輸出測資組編號，如果無法搜集到所有食物，則輸出 ‘Impossible’。

反之分別輸出最短路徑長及路徑個數，輸出 mod 20437 後的結果即可。

Sample Input                             Output for Sample Input

5 A.... ####. ..B.. .#### C.DE. 2 A. .B 2 A# #B 0

Case 1: 15 1 Case 2: 2 2 Case 3: Impossible

11655 - Waterland

西元 3110 年，大多數的陸地已經陷入水中，只剩下少數的島嶼。水島是由許多小島嶼所組成，所有小島嶼間藉由隧道連接，每個隧道兩端確切只有 2 個島嶼。

水島總統想要去 Yablonoi 島度假，精英安全部隊必須要護送總統從 Kurai 島到 Yablonoi 島，他們必須選擇安全的隧道來前進。在每種可能路徑中，每條隧道都只能經過一次。

安全部隊每次派出有很多小隊一起出發，嘗試每種不同的路徑，每經過島嶼時，會留下一個小隊駐守，每次都只會剩下一個小隊抵達 Yablonoi 島，而一座小島可能會有多個小隊來自於不同次出發的。

現在安全部隊的負責人要計算總共派發出的小隊個數，並且計算有多少個小隊抵達目的地。

Input

測資第一行有一個整數 N (N < 40)，表示測資組數。

對於每組測資，第一行會有兩個整數 L, T (2 <= L <= 5000, 0 <= T <= 5*L)，分別表示島嶼個數，以及安全隧道的個數。

接下來會有 T 行，每行上有兩個整數 x, y (1 <= x, y <= L)，表示有一條有向隧道從 x 到 y。對於任兩個島嶼間最多有一條隧道連接，而島嶼編號 1 為 Kurai 島，島與編號 L 為 Yablonoi 島。

Output

對於每組測資，輸出測資組編號，以及兩個整數 S, D，分別表示總共需要的小隊數，以及最後抵達目的地的小隊總數。

只需打印出 mod 100000 的結果即可。

Sample Input                              Output for Sample Input

3 2 1 1 2 4 4 1 2 1 3 2 4 3 4 4 3 1 2 2 3 3 4

Case 1: 1 1 Case 2: 4 2 Case 3: 3 1

986 - How Many

在一個平面上的格子點中，考慮每次步驟為加上 (1,1) 或 (1,-1)，並且不會低於 x 軸，而每個山頂高 k 定義為在 (1,1) 步驟後 y=k 且緊接著 (1,-1) 步驟。

如下圖所示，左圖有 4 個山頂，其中 2 個山頂高度 2，另 2 個山頂高度 3。

右圖則有 3 個山頂，高度分別為 1, 2, 3。

Problem

從 (0, 0) 出發，中止於 (2n, 0)，並且確切存在 r 個山頂高度 k。

Input

輸入有多組測資。

每組一行有 3 個整數 n, r, k。
(1 <= n < 20, 0 <= r < 20, 1 <= k < 20)

Output

對於每組測資輸出一行，一個整數表示有多少種路徑走法， 答案小於 2³¹。

Sample Input

3 1 2
10 3 2

Sample Output

2
2002

10350 - Liftless EME

EME 建築在 2002 年到 2020 年間越建越高，但是電梯數量仍維持定量。因此這對於學生到教室是個很重要的問題，對於 ACM 練習賽的選手特別重要，比賽從每個星期二的 2:00 pm 開始，此時電梯和樓梯都擠滿了實驗室的學生。

所有參賽選手打算抄捷徑到 ACM 教室，他們偷偷地在每一層天花板挖洞，並且每個洞向下放置一個樓梯，因此他們可以藉由這些到達另一個樓層，藉以避面大批人群。

問題為：現在有很多捷徑，計算一個最短路徑抵達目的地。

目標從地面 (0 層)  到達頂樓 (n-1 層)，特別注意參賽者只會往上爬。

Input

輸入有多組測資。

對於每組測資，第一行會有一個測資組名稱，長度不超過 12 字元。

接著會有 2 個整數 n, m，分別表示 EME 建築的樓層數量、每一層有的洞數量。

接下來會有 m(n-1) 行，每行上會有 m 個整數，在第 k*m+i 行上，表示在第 k 層的第 i 個洞的資訊，該行的第 j 個整數表示到第 k+1 層的第 j 個洞的時間。

(0 <= k < n-1 < 120, 1 < i, j < m <= 15)

Output

對於每組測資輸出兩行，第一行為測資組名稱，第二行為最少時間從地面到頂樓。

Sample Input

Sample001

3 2

1 2

3 4

5 6

7 8

Sample Output

Sample001

10

1198 - The Geodetic Set Problem

G = (V, E) 表示一連通圖，不存在 loops(自己連自己) 和重覆的邊，V, E 分別表示節點與邊。

對於 u, v ∈ V 必然會存在一條最短路徑，而 I (u, v) 定義為在 u - v 最短路徑上的點所產生的集合，而 S ⊆ V，

如果 I(D) = V，則這節點集合 D 被稱作為 G 的其中一個 geodetic set， The geodetic set problem 就是要檢驗 D 是否為 geodetic set。

以上圖為例，I(2, 5) = {2, 3, 4, 5}，即所有可能在最短路徑上的所有點，然而
I(2, 5) 並不是一個 geodetic set，因為並不等於 {1, 2, 3, 4, 5}。

假如 D = {1, 2, 5}，則 I(D) = V，同時 {1, 3, 4} {1, 4, 5} 也都是 geodetic set，但
{3, 4, 5} 卻不是，因為節點 1 並不在 I(D) 中。


Input

輸入有多組測資，每組第一行有一個整數 n (2 <= n <= 40) 表示圖有多少節點。

接下來會有 n 行，在第 i 行(1 <= i <= n)上會有數個整數，表示與節點編號 i 相連的點。

接著會有一行一個整數 q，表示接下有多少組詢問。
 
每組詢問一行，行上的每個整數 D 集合內的節點編號。
Output

對於每組詢問的 D，判斷 D 是否為 geodetic set。

Sample Input

5
2 3
1 3 4
1 2 5
2 5
3 4
6
1 2 3 4 5
1 2 5
2 4
1 3 4
1 4 5
3 4 5
 
Sample Output

yes
yes
no
yes
yes
no

925 - No more prerequisites, please!

最近，我正在準備給予少部分學生的畢業課程指導，向同事要課程之間的關係，而有部分課程需要先修課程，定義這先修課程的集合為 c，也就是說學生必須先修過 c 的所有課程，才能修這門課。

不過同事太熱心了，給了過多的資訊，過多是什麼意思，接下來我會解釋 ...：

• 假設有課程名為 ca, cb, cc, cd, cd
• 必須先修過 ca 才能修 cb；必須先修過 cb 和 cc 才能修 cd；
  必須先修過 cd 才能修 ce。
• John 負責課程 cd，告訴我先修課程為 cc, cb, ca。
• Elizabeth 負責課程 ce，告訴我先修課程為 cd, cc, cb, ca。

但我發現只需要說明先修課程 cc, cb，就可以修 cd 課程，因為 ca 已經在 cb 的先修課程中。同樣地，只需要說明 cd 是 ce 的先修課程即可，因為 cd 已經有 cc, cb, ca 的先修課程條件了。

不幸地，並不是每個同事都給予最小化的先修課程，太多太多的資訊蜂擁而來，希望有個機器人可以幫忙處理這些資訊，並寫告訴我最小化的先修課程。


Input

輸入第一行有一個整數，表示接下來會有多少測資組，至多 1000 組。

每組第一行會有一個整數 k，表示課程總數，而接下來會有 k 行，分別為課程名稱。
課程名稱由小寫英文字母構成，長度最多為 20。

接下來有一個整數 j，表示接下來有 j 行先修課程的資訊。
每一行第一個為課程名稱，第二個整數為先修課程的個數，接下來為先修課程的名稱。

(0 < k, j <= 120)

Output

按照輸入順序，依序輸出該課程的先修課程清單，對於先修課程清單同樣按照輸入順序輸出。

Sample Input

2
5
cc
ca
ce
cb
cd
3
ce 4 cd cb cc ca
cd 3 cb cc ca
cb 1 ca
9
dg
di
dc
df
de
dd
da
dh
db
7
dg 3 da de df
dd 2 da db
df 1 de
dc 1 db
dh 5 da de dg df dc
de 2 da dd
di 2 df dd

Sample Output 

cb 1 ca
cd 2 cb cc
ce 1 cd
dc 1 db
dd 2 da db
de 1 dd
df 1 de
dg 1 df
dh 2 dc dg
di 1 df