※ 引述《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