作者DJWS (...)
看板Prob_Solve
标题Re: [问题] ACM UVa10160 Servicing Station
时间Thu Oct 14 18:00:44 2010
抱歉回文回得有点慢...
我用的方法是backtracking
穷举n个0/1数字的所有排列
（类似於穷举所有子集合）
递回过程当中
甲、随时计算目前被服务到的城市有哪些
乙、也随时判断目前的排列是不是合理的
丙、也随时纪录目前的最佳解！可以做bound！
因为这题的n值有点大
所以我用了一些小技巧来避免TLE
一、
纪录地图的资料结构
我用的是adjacency lists
这样可以节省一点时间
二、
纪录城市有被/没被服务
我用了一个类似於counting sort的阵列
如果城市x有被服务到 就count[x]++;
如果城市没被服务到就不加加
这样可以节省一点时间
程式码也会变得很优雅
三、
一开始我先把每个城市都放上服务站
把count[x]统统累加好
执行回溯法的时候
则是使用消去/不消去服务站两种选择
这样子倒行逆施有一个好处
就是每当发现有一个城市没有被服务到（count[x] <= 0）
马上就可以剪枝！
四、
我用了一个bound
当递回到第m层时
第1~m的城市共留有c个服务站
此时
如果把m+1~n的服务站全部去掉之後
发现没有比最佳解好到哪里去（c - (n-m) >= ans）
就算继续递回下去也没意义
马上就可以bound！
（这个不是A*喔...就是branch and bound的bound！）
我用的方法大致上是这样
如果有需要我再寄程式码给你，不用客气！
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.115.153.221
※ 编辑: DJWS 来自: 59.115.153.221 (10/14 18:04)
※ 编辑: DJWS 来自: 59.115.153.221 (10/14 18:05)
※ 编辑: DJWS 来自: 59.115.153.221 (10/14 18:11)
※ 编辑: DJWS 来自: 59.115.153.221 (10/14 18:16)