演算法高階・圖的進階搜尋
BFS 著色判斷能否分兩組、Kruskal 加併查集的最小生成樹、位置加鑰匙遮罩的狀態 BFS。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
衝突任務分兩個時段
困難圖夜間批次有 n 個任務(編號 1 到 n),要分到 A、B 兩個時段跑。有些任務兩兩衝突(會搶同一張表的鎖),衝突的兩個任務必須在不同時段。請判斷能不能分;能分的話,照下面的規則決定唯一的分法並印出兩個時段各有幾個任務。
規則:把任務與衝突關係看成圖,每個連通的群組裡編號最小的任務放 A 時段,同群組其他任務的時段就被衝突關係決定;沒有任何衝突的任務自己就是一個群組,放 A。
輸入:
第 1 行:組數 t
接下來 t 行:
n後面接若干個衝突a-b(以空白分隔;可能沒有任何衝突;同一對可能重複出現;a-a表示任務 a 跟自己衝突,這種情況一定分不了),或n GEN m seed(由 starter 產生 m 個衝突)。GEN開頭的行是大量測資的縮寫:starter 已寫好產生資料的函式,讀進來後跟一般的資料一樣,不用自己處理。輸出:每組一行
- 能分:
YES A時段任務數 B時段任務數 - 不能分:
NO 編號,編號是「分不了的群組」中最小的任務編號;有多個群組分不了時,取這個編號最小的那一個
要求:用 BFS 著色,任務編號由小到大當起點,一個群組一個群組處理;n 可能有幾千,不要列舉所有分法。
範例輸入:
2
4 1-2 1-3 1-4
3 1-2 2-3 1-3
範例輸出:
YES 1 3
NO 1
類型對應:LeetCode「Possible Bipartition」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 能分:
- 02
叢集專線最低建置成本
困難最小生成樹新機房有 n 個節點(編號 1 到 n),網路組列出了可以拉的專線,每條連接兩個節點、有建置成本。要挑一些專線讓所有節點彼此連通(可以經過別的節點),總成本最低。最低成本的挑法可能不只一種,但總成本與「挑中的專線裡最貴的那條」的成本是固定的,請印出這兩個數。
輸入:
第 1 行:組數 t
每組:第 1 行是
n m(節點數、候選專線數),接下來 m 行是a b 成本(a ≠ b,成本是正整數,同一對節點可能有多條);或第 1 行是
n m、第 2 行是GEN seed lo hi(由 starter 產生 m 條專線,成本在 lo 到 hi 之間)。GEN開頭的行是大量測資的縮寫:starter 已寫好產生資料的函式,讀進來後跟一般的資料一樣,不用自己處理。輸出:每組一行
- 能全部連通:
MST 總成本 最貴一條的成本(n = 1 時不用拉線,印MST 0 0) - 不能全部連通:
DISCONNECTED 群組數,群組數是用所有候選專線連完之後,彼此不相連的節點群有幾個
要求:用 Kruskal 演算法:專線依成本由小到大排序,用併查集(union-find)判斷兩端是不是已經相連,相連就跳過;m 可能有幾千條。
範例輸入:
1
3 3
1 2 4
2 3 1
1 3 2
範例輸出:
MST 3 2
類型對應:LeetCode「Connecting Cities With Minimum Cost」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 能全部連通:
- 03
機房巡檢收齊門禁卡
困難BFS機房的平面圖是一個 r×c 的格子:
@是巡檢人員的起點,.是走道,#是機櫃(不能走),小寫字母a到f是門禁卡,大寫字母A到F是門。拿到門禁卡a之後才能通過門A,依此類推;走到門禁卡的格子就自動拿到,拿到後一直有效。每一步可以往上下左右走一格,不能走出平面圖。每種門禁卡最多一張;有些門可能沒有對應的門禁卡,那扇門永遠過不去。請算出收齊平面圖上所有門禁卡最少要走幾步。
輸入:
第 1 行:組數 t
每組:第 1 行是
r c,接下來 r 行各是長度 c 的字串輸出:每組一行,最少步數;收不齊時印
-1;平面圖上沒有門禁卡時印0。要求:用 BFS,狀態是「位置+手上有哪些門禁卡」,門禁卡集合用位元遮罩表示;同一個位置手上的卡不同,要當成不同的狀態。
範例輸入:
1
2 4
@.aA
..#b
範例輸出:
4
類型對應:LeetCode「Shortest Path to Get All Keys」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了