PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] ACM UVa10160 Servicing Station

看板Prob_Solve (計算數學 Problem Solving)作者 (薩哈拉雅)時間14年前 (2010/10/03 14:16), 編輯推噓2(2推 0噓 11→)
留言13則, 5人參與, 最新討論串1/5 (看更多)
小弟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
→
10/03 14:31, , 2F
只有上np的時候聽過,只知道很難,也沒解過 Orz
10/03 14:31, 2F
→
10/03 14:31, , 3F
但是 wiki 下面可能有一些 link 有幫助
10/03 14:31, 3F
推
10/03 15:18, , 4F
嗯...我只剪了兩個地方
10/03 15:18, 4F
→
10/03 15:18, , 5F
一個是,如果當前這個用了 卻不能蓋到更多點 就不遞迴下去
10/03 15:18, 5F
→
10/03 15:18, , 6F
另一個是, 如果當前這個點不用, 會造成有點覆蓋不到,就用
10/03 15:18, 6F
→
10/03 15:19, , 7F
還有位運算...
10/03 15:19, 7F
→
10/03 15:46, , 8F
To S大: 1. 不能蓋到更多點是指至少要能蓋到一個未被服務的
10/03 15:46, 8F
→
10/03 15:46, , 9F
點媽?
10/03 15:46, 9F
→
10/03 15:47, , 10F
2. 位元運算用在哪呢?? 我都是直接生memory出來 xd
10/03 15:47, 10F
→
10/03 16:17, , 11F
1.是的 2.我用一個long long表示哪些點已經被蓋到了
10/03 16:17, 11F
→
10/03 18:50, , 12F
只要1.的剪枝就可以AC了。原po先嘗試剪枝後再改bit版本
10/03 18:50, 12F
推
10/20 17:49, , 13F
應該是 'dominating set' 不是 'vertex cover'
10/20 17:49, 13F
‣ 更多 rifiz 的文章
文章代碼(AID): #1Cg1_I14 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 rifiz 的文章
文章代碼(AID): #1Cg1_I14 (Prob_Solve)