#38615: DFS+剪枝


wrr606@gmail.com (Function)

學校 : 國立金門大學
編號 : 133433
來源 : [1.174.35.228]
最後登入時間 :
2024-04-29 14:36:16
a523. 12442 - Forwarding Emails -- UVa12442 | From: [1.174.38.241] | 發表日期 : 2023-12-10 18:07

直接用一般的 DFS 把每個節點跑一遍會吃 TLE,所以要進行剪枝,

 

因為每個節點都只會單向的指向一個目標,所以節點間的連線圖都會形成一個環,

 

假設 1 會到 2,由 1 開始 DFS 的節點連接數是 n,那 2 開始 DFS 的節點連接數會是 n-1

 

因此在每一次 DFS 後,都不需要再去 DFS 先前跑過的節點,因為節點連接數一定比較少,而這就是這題的剪枝方法了

 
#38616: Re: DFS+剪枝


wrr606@gmail.com (Function)

學校 : 國立金門大學
編號 : 133433
來源 : [1.174.35.228]
最後登入時間 :
2024-04-29 14:36:16
a523. 12442 - Forwarding Emails -- UVa12442 | From: [1.174.38.241] | 發表日期 : 2023-12-10 18:12

重新修改一下前面有講錯的部分

直接用一般的 DFS 把每個節點跑一遍會吃 TLE,所以要進行剪枝,

 

因為每個節點都只會單向的指向一個目標,所以節點間的連線圖都會形成一個環,

 

假設 1 會到 2,由 1 開始 DFS 的節點連接數是 n,那 2 開始 DFS 的節點連接數會是小於或等於 n 的數

 

因此在每一次 DFS 後,都不需要再去 DFS 先前跑過的節點,因為節點連接數一定比較少或是一樣,這題只需要找最大的節點連接數

 

這樣就可以減少 DFS 的次數了

 
ZeroJudge Forum