作者rifiz (薩哈拉雅)
看板Prob_Solve
標題[問題] ACM UVa10160 Servicing Station
時間Sun Oct 3 14:16:47 2010
小弟online judge在這題卡住了 : Problem D: Servicing stations
這題是給一群city 還有一堆city之間的connection. 然侯要找出能cover所有city的
service station的最小數目. 一個station可以服務所在地的所有immediate city.
我使用的方法是 backtracking, 也就是暴力法的一種. 這種方法的精華應該是在
剪枝 但是我沒辦法減到足夠少的狀態數目 有誰可以給個建議要如何減少才行嗎?
目前我的剪枝只有: 比上一次的數目多的話就不搜尋了 XD
請先進給我一點想法跟意見阿.......感激不盡
--------------------
已經TLE好幾百次了 @_@
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.199.110
※ rifiz:轉錄至看板 C_and_CPP 10/03 14:17
2F：→ yoco315:只有上np的時候聽過,只知道很難,也沒解過 Orz 10/03 14:31
3F：→ yoco315:但是 wiki 下面可能有一些 link 有幫助 10/03 14:31
4F：推 suhorng:嗯...我只剪了兩個地方 10/03 15:18
5F：→ suhorng:一個是,如果當前這個用了 卻不能蓋到更多點 就不遞迴下去 10/03 15:18
6F：→ suhorng:另一個是, 如果當前這個點不用, 會造成有點覆蓋不到,就用 10/03 15:18
7F：→ suhorng:還有位運算... 10/03 15:19
8F：→ rifiz:To S大: 1. 不能蓋到更多點是指至少要能蓋到一個未被服務的 10/03 15:46
9F：→ rifiz:點媽? 10/03 15:46
10F：→ rifiz:2. 位元運算用在哪呢?? 我都是直接生memory出來 xd 10/03 15:47
11F：→ suhorng:1.是的 2.我用一個long long表示哪些點已經被蓋到了 10/03 16:17
12F：→ bleed1979:只要1.的剪枝就可以AC了。原po先嘗試剪枝後再改bit版本 10/03 18:50
13F：推 DJWS:應該是 'dominating set' 不是 'vertex cover' 10/20 17:49