※ 引述《rifiz (薩哈拉雅)》之銘言： : 小弟online judge在這題卡住了 : Problem D: Servicing stations : 這題是給一群city 還有一堆city之間的connection. 然侯要找出能cover所有city的 : service station的最小數目. 一個station可以服務所在地的所有immediate city. : 我使用的方法是 backtracking, 也就是暴力法的一種. 這種方法的精華應該是在 : 剪枝 但是我沒辦法減到足夠少的狀態數目 有誰可以給個建議要如何減少才行嗎? : 目前我的剪枝只有: 比上一次的數目多的話就不搜尋了 XD : 請先進給我一點想法跟意見阿.......感激不盡 : -------------------- : 已經TLE好幾百次了 @_@ 還是TLE. @_@ vertex cover那個好難 現在看不是很懂.....XD 小弟我的做法大概是: BackTrack 1. 檢查現在的station數目 比之前的所有解的最小數目還大的話 就return 2. 產生可能的candidate list: A. 對所有還沒有被服務到的city, check: 這個city所連出去的的city是不是至少有一個還沒被服務到, 是的話才加入 candidate list. 3. For each candidate: A. append到solution list的尾端 B. 把被他服務到的city mark起來 C. BackTracking. 有試過如下的剪枝: 每次選擇的點所造成的cover set每一步都要 > 上一次的每一步的cover set, 可是這樣 會錯(事實上也找的出反例 XD) 但是上面這樣的剪枝應該還是不夠, 看了各位大大的建議只能得出上面的做法..... 請幫忙再建議一下該如何在哪裡剪枝...... 謝謝各位 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.43.199.110