作者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