[問題] ACM UVa10160 Servicing Station

[rifiz (薩哈拉雅)]

小弟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
→ yoco315:http://en.wikipedia.org/wiki/Vertex_cover_problem
→ yoco315:只有上np的時候聽過,只知道很難,也沒解過 Orz
→ yoco315:但是 wiki 下面可能有一些 link 有幫助
推 suhorng:嗯...我只剪了兩個地方
→ suhorng:一個是,如果當前這個用了 卻不能蓋到更多點 就不遞迴下去
→ suhorng:另一個是, 如果當前這個點不用, 會造成有點覆蓋不到,就用
→ suhorng:還有位運算...
→ rifiz:To S大: 1. 不能蓋到更多點是指至少要能蓋到一個未被服務的
→ rifiz:點媽?
→ rifiz:2. 位元運算用在哪呢?? 我都是直接生memory出來 xd
→ suhorng:1.是的 2.我用一個long long表示哪些點已經被蓋到了
→ bleed1979:只要1.的剪枝就可以AC了。原po先嘗試剪枝後再改bit版本
推 DJWS:應該是 'dominating set' 不是 'vertex cover'