集训队作业游览计划trip解题报告

1、WinterCamp2008, Trip Report Yali 游览计划(Trip)解题报告 雅礼中学 陈丹琦问题简述 给你一个m * n的加权非负矩阵，要求从中选出一些方格，使得任意两个0权方格中都至少存在一条由选出的方格组成的路径，并且要求选出的方格权和最小数据规模：，其中k为0权方格的个数算法分析 m, n, k非常小，我们很容易联想到用基于状态压缩的动态规划来解决下面从两种不同的角度提出两种状态压缩的动态规划的算法并对它们进行比较：【算法一】基于连通性状态压缩的动态规划问题可以转化为：一个m * n的加权非负矩阵，要求找到一个连通块使得连通块内所有方格权值之和最小，且所有的0权方格必

2、须包含在这个连通块中在笔者今年国家集训队论文基于连通性状态压缩的动态规划问题里面对这一类问题作过详细的介绍，下面简单地来介绍一下算法：按照从上到下，从左到右的顺序依次来考虑每一个格子，设f (i, j, S)表示当前考虑完(i, j)这个格子后，轮廓线上从左到右n个格子的连通标号为S这个状态下方格权和的最小值注意S使用最小表示法，连通的格子标记上相同的数字，没有选的格子标记为0，如右边图中，黑色格子表示选择了的格子，灰色格子表示轮廓线上没有被选择的格子，那么S = 1, 0, 2, 0, 2, 0，对于本题的数据规模来说，最多出现5个连通块，建议使用8进制来存储S的状态考虑状态的转移：根据当前

3、格子的左边格子和上面的格子是否选择分情况进行讨论，可能新建一个连通块，可能合并两个连通块，可能延续原来的连通块，计算新的状态的最小表示即可，转移的代价为O(n)实现的时候建议使用宽度优先搜索的形式，使用滚动队列，然后用Hash表来判重，每一次从(i, j)到(i, j+1)的转移Hash表清空因此的总的时间复杂度为O(扩展的状态总数 * n)，状态总数主要取决于m, n的大小，k的大小也会间接影响到扩展的状态总数(k越大，必须被选择的格子就越多，那么扩展的状态总数就会减小)，对于第8号测试点，m = n = 10，k = 3的最坏情况，扩展的状态总数为639452，是完全可以承受的最慢的测试点

4、在0.2s内可以运行出来 测试环境： 测试环境：Intel Core2 Duo T7100, 1.8GHz, 1G内存这种算法的效率受m, n的大小的影响非常大，当m, n 13的时候，扩展的状态总数已经非常多了，算法已经不再适用下面提出另一种算法，它的效率主要取决于k的大小【算法二】注意本题的数据规模k很小，最多为10，远远达不到O(mn)的级别，可以以此为突破口来分析问题设状态f (i, j, S)表示以(i, j)为汇合点，k个0权方格是否已经与(i, j)连通的二进制状态为S，这个状态下选中方格的最小权和考虑状态的转移，主要有两种情况：1)合并，其中为S的子集，这种情况下相当于将两个以

5、(i, j)为汇合点的不相交的集合进行合并延续 ，其中与(i, j)相邻，这种情况相当于修改汇合点考虑算法的实现，从小到大枚举S：转移1)，枚举S的所有非空真子集，可以通过搜索找出S的所有子集，有一个小的技巧可以无重复无遗漏地枚举所有的：Repeat If () Then Break Until False考虑二元组()，其中为S的子集，那么每个元素要不在中，要不在中或者不在中，因此共有3k个这样的二元组，因此转移1)的总代价为O(m * n * 3k)转移2)，是在同一个S的之间进行转移，这个可以用最短路算法来进行转移，如果使用SPFA算法，时间复杂度为O(E) = O(mn)，因此转移2)的总代价为O(m * n * 2k)因此这个算法总的时间复杂度为O(m * n * 3k)，最慢的测试点为0.08s，对于本题的数据规模来说效果非常好 小结上述我们提出了两种思考角度不同的状态压缩算法，从本题的数据规模出发，算法二的程序效率更高，编程复杂度更低不过我们很难衡量这两个算法孰优孰劣，当m = n = 20，k = 10，算法一