#9: DFS解題法


algasami (Kyuushin Kushinada)

School : 花蓮高中
ID : 210
IP address : [101.12.89.218]
Last Login :
2023-09-27 11:52:39
c005. 元件測試排程問題 | From: [59.115.32.220] | Post Date : 2022-08-16 11:36

DFS解題法

這題的遮罩最大(2^26 - 1)不超過INT_MAX,所以可以直接用整數做bitmask。

基本上可以用DFS解。

大前提:

  1. 產生的圖要是DAG,否則是Order Conflict
  2. 以生成樹來看時由樹葉到根與根到樹葉只能有一種答案(Tip: 樹葉到根用reverse(algorithm標頭檔)

BITMASK實作:

關於Bitmask在DP的實作請參考Geeks For Geeks - Bitmasking and Dynamic Programming

用Bitmask偵測Order Conflict:

如果遇到元件的依賴bitmask有現在要被依賴的原件時(compPtr->pre & (1 << b))即為Order Conflict,反之亦然。

元件的依賴與被依賴bitmask用回朔遞迴一個一個展開。

產生生成樹:

搜尋所有1. 依賴bitmask為0 2.被依賴bitmask為0 的原件,分別做下至上dfs(依賴bitmask = 0代表樹葉)與上至下dfs,

如果兩種都有解果就看reverse(下至上dfs)的答案與上至下相不相同。

輸出答案:

要有個cycleIndex,如果有cycle就輸出(預設-1 == 沒有)

如果沒有答案或many是真值(多種解法),輸出No Answer

不然直接輸出答案

 
ZeroJudge Forum