集训队作业boxes解题报告

1、IOI2003 中国国家集训队难题活动0018Boxes解题省芜湖市第一中学【题目大意】给出 N 个排成一圈的盒子，依次顺时针为 1,2,N，每个盒子 i 有且仅有一个顺时针方向上的邻居 i+1(若 i=N 则为 1)和一个逆时针方向上的邻居 i-1(若 i=1 则为 N)。第 i 号盒子中初始时已经摆放了 Bi 个球，每一步可以把某一个球从原先所在的盒子移动到这个盒子的顺时针或逆时针邻居内。现要使所有的盒子里面最多只有一个球，求最少需要移动多少步。题目保证所有的球的总数 M 不超过 N(否则显然无解)。【解决情况】采用最小费用流求解，时间复杂度为 O(kMN)，其中 k 为一个不确定的系数，

2、通常 k 可以看作一个不太大的常数，因此时间复杂度可看成 O(N2)。空间复杂度为 O(N)。【算法梗概】构造出合适的网络流的模型，使每个流对应着一个球以及它最终所在的盒子，同时这个流上的总费用对应着这个球移动的步数，构造出的网络图满足 O(E)=O(V)。最后就是要求总费用最小，总流量为 M 的一个流，因此需要从 0 流扩展 M 次，每次首先采用 SPFA算法找一条费用最小的增广路径，复杂度为 O(kN)，再用这个增广路径扩展可行流，复杂度为 O(N)，所以总的时间复杂度为 O(kMN)。【正文】看了题目，可以有两种思路：第一种是动态规划，目前已知的最好方法似乎只是O(n3)的，比较不能接受

3、。第二种是最佳匹配或者最小费用流，也就是本文将算法。匹配或流的是很自然的：最终每个球都必须在某个盒子内，但每个盒子最多只能放一个球，球原来所在的位置到最终的位置的距离就是这个球转移的最小步数。所以很容易想到：以球为点集 A，盒子为点集 B，每个盒子 i 中所有的到每个盒子 j 都有一条边，权值就是盒子 i 到 j 的最短距离(顺时针距离和逆时针距离的最小值)。这样建立的就是一个二部图的模型。例如对于 5 个盒子 1,2,3,4,5，其中摆放的球分别有 0,1,0,2,1 个，则建立出的是如下的一个图：15图中的圆圈代表球，从左到右分别是 2 号盒子,4 号盒子,4 号盒子以及 5 号盒子内的球

4、。方格代表盒子，方格内的数字是盒子的。每个球到每个盒子都有边，边上的数字代表其权值，也就是球原先所在的格子到边所连的格子的最短距离，没有标数字的边是一条权值为 0 的边。很显然，在这个二部图中求使所有匹配边权值和最小的一个最佳匹配，其最小权值和就是要求的 。又或者 把原来在同一个盒子中的球并到一个结点，添加一个源 S 和一个汇 T，用 S到每个 A 类点的边的容量代表同一个盒子中原先有球的总数，费用为 0。每个 A 类点到每个 B 类点有一条容量为 1 的边，代表最终可以把一个球转移到边所连的盒子内，边的费用为起点代表的球到终点所代表的盒子的最短距离。每个 B 类点到 T 有一条容量为 1，费

5、用为0 的边，代表每个盒子最多可以放一个球。例如同样是上面的例子，可以建立下图：S21111T图中 S 到圆圈的边上的数字代表容量，除了 S 到圆圈的边，其它边的容量均为 1。圆圈到方格的边上的数字代表费用，也就是转移的最少步数，未标出数字的费用为 0，除了圆圈到方格的边，其它边的费用均为 0。不难看出，在这个图里求从 S 到 T 的最小费用最大流，求出的最小费用就是要求的。以上两种方法的本质都是相同的：直接建立每个有球的位置到所有盒子的关系，因此建立出的都是二部图的形式，并且每个 A 类点到每个 B 类点都有边。在这种图内无论是求最佳匹配还是求最小费用最大流，其复杂度都是 O(MVE)级别，

6、其中 M 是球数，V 是顶点数，它们的规模都是 O(N)，E 是边数，规模为 O(N2)，因此整个复杂度高达 O(n4)，显然是不可接受的。以上建立的图论模型之处在于它不能很好地体现出转移的连续性，也就是一个球转移到离原来的盒子距离为 d+1 的盒子之前，它一定先转移到了距离为 d 的盒子内，而转移到距离为 d+1 的盒子内的费用是转移到距离为 d 的盒子内的费用加 1。为了体现这种特性，建立第二个网络流模型：设一个源 S 和一个汇 T。每个盒子对应一个顶点，如果一个盒子 I 有 b 个球，那么就连有向边 S-I，容量为 b，费用为 0，一个S-I 的流就代表盒子 I 中的一个球。对每个盒子

7、I 都连一条有向边 I-T，容量为 1，费用为 0，一个 I-T 的流就代表最终有一个球转移到了盒子 I 并定下来。每个盒子 I 项它的顺时针邻居 J 连一条有向边 I-J，容量为无限，费用为 1，代表转移到了盒子 I 的球可以5向 J 转移，花费一步。同理，每个盒子 I 向它的逆时针邻居 H 连一条有向边 I-H，代表转移到了盒子 I 的球可以向 H 转移，花费一步。同样对于开头下的模型：例子，可以建立如S211T图中 S 到方格的边上的数字表示容量，费用均为 0。方格之间的边容量均为无限，费用均为 1。方格到 T 的边容量均为 1，费用均为 0。不难看出，在这样构造出的图中求 S 到 T

8、的最小费用最大流，求出的最小费用也就是所要求的最少移动步数。建立的第二个网络流模型最多只有 4N 条边，因为方格点之间有 2N 条边，方格点到 T 有 N 条边，S 到方格点最多只有 N 条边。也就是说，这个模型中 O(E)=O(V)=O(N)。这是一个很 Sharp 的性质，下面将会看到它起了的作用。对建立起来的网络图求最小费用最大流，如果采用所谓“先流推进”(PreFlow_Push)方法的话，似乎是 O(sqrt(E)*V)级的，但是作者不是很清楚这种方法，所以典的求增广路径的方法。每次在当前的图中找一条费用最小的增广路径，实际上就是以 S 为源点，把当前图中每条未满边看作距离等于费用的

9、边，把每条有流量的边看作距离为费用相反数的边，求 S到T 的最短路。由于可能出现负边，所以要采用迭代法来求这个最短路。如果用 Bellman_Ford来实现迭代，则每次求最短路的复杂度为 O(VE)=O(N2)，而根据求出的增广路径扩展可行流的复杂度为 O(N)。最大的流量肯定是 M，所以总的复杂度为 O(MN2)=O(N3)。理论上比较高，但实际往往很难达到 情况，因此效果还是比完全 O(N3)的动态规划要好的。采取更有效的迭代方法来求增广路径(也就是最短路)，即所谓 SPFAShortest Path Faster Algorithm，它可以在 O(kE)的时间复杂度内求出源点到其他所有点

10、的最短路径，可以处理负边。SPFA 的实现甚至比 Dijkstra 或者 Bellman_Ford 还要简单：设 DistI代表 S 到 I 点的当前最短距离，FaI代表 S 到 I 的当前最短路径中 I 点之前的一个点的 。开始时 Dist 全部为+，只有 DistS=0，Fa 全部为 0。一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点 S。用一个还是采用经数组每个点是否处在队列中。每次迭代，取出队头的点 v，依次枚举从 v 出发的边 v-u，设边的长度为 len，判断 Distv+len 是否小于 Distu，若小于则改进 Distu，将 Fau记为 v，并且由于 S 到

11、u 的最短距离变小了，有可能 u 可以改进其它的点，所以若 u 不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是 S 到所有的最短距离都确定下来，结束算法。SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就51432不可能重新进入队列，但是 SPFA 中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为 k，有办法证明对于通常的情况，k 在 2 左右(怎么证明的作者也不知道)。由于所有的点分别作一次迭代点进行

12、改进的复杂度为 O(E)，所以整个算法的复杂度为 O(kE)=O(E)。注意到这里又有一个看似不正确的地方k 是所有点作迭代点的平均次数，而每个点的边数是可能不同的，如果边比较多的点作迭代点的次数很多的话，复杂度应该就不止 O(kE)了，但是似乎又可以证明不会出现的情况，不过本题中出了 S 之外，所有的点都只有常数条边，而 S 显然不会多次迭代，所以不需要考虑这个问题。总之，SPFA 理论上的复杂度为 O(kE)，而作者对于本题的数据进试，发现对大部分数据，k 都小于 1！只有极少数的数据中 k 达到了 1，没有超过 1 的，也许这可以从本题的图的特殊性质证明吧。用 SPFA 可以在 O(kE

13、)的时间复杂度内求出最短路（也就是增广路径），用增广路径来扩展可行流的时间复杂度为 O(V)，而这里 O(E)=O(V)=O(N)，所以可行流扩展一次的时间复杂度为 O(kN)，而可行流扩展 M 次之后达到最大，因此整个算法的时间复杂度为 O(kMN)，可以看成 O(N2)，非常好了。空间复杂度可以控制在 O(N)，因为除 S 外，每个点出发的边为常数，而从 S 出发到每个点最多只有一条边，存整个图的复杂度可以做到 O(N)，而 SPFA 中用到的 Dist,Fa 以及布尔数组都是 O(V)规模的，只有一个队列不好估计应该开多长，但是没有关系，因为任意时刻队列中不会有两个相同点，因此如果用循环

14、队列来实现，只需要长度为 N 的数组就可以了。在解决本题的过程中，根据先构造了本质相同的一个匹配和一个网络流模型，但是发现这两个模型不能充分利用到题目的条件，使算法的复杂度太高，所以构造了第二个网络流的模型，很好地切合了题目的本质，使得构造出的图边数与点数同阶，然后了 SPFA 方法求最短路，最终把时间复杂度做到了实际意义上的 O(N2)。采用可见，构造模型要尽量精确，尽可能利用到题目中的条件。对同一个模型，要选择合适的算法去求解它。本题程序见 kul.pas。【进一步研究的方向】1.2.可以考虑用 PreFlow_Push 方法来求最小费用最大流，这样复杂度又可以降低。标准是这样的：数组it

15、ion1.n非零的格子的位置，Rest1.n对应的非零的格子的小球数减。ClockWise1.n每个非零格子需要顺时针转移的最远的位置，lockWise1.n每个非零格子需要逆时针转移的最远的位置ition 和 Rest 根据输入确定，ClockWise和lockWise 开始都等于ition，也就是原来所在的位置。依次处理每一个点 i，如果Resti0，就算出这个点顺时针和逆时针转移一个球的 Cost，选择较小的一个，转移。计算Cost 的方法，顺时针和逆时针是对称的，以顺时针为例：假设顺时针地转移，那么会导致 ClockWisei改为顺时针的下一个（相应地，要增加一定的转移步数），然后判断lockWisej是否等于 ClockWisei，其中 j 为 i 的顺时针的下一个非零格，若等于，则lockWisej改为顺时针的下一个，同时 ClockWisej改为顺时针的下一个，并更改 Cost中的转移步数。这样，等于是 j 又向顺时针转移了一个，可能会造成连锁的反应，所以要继续判断下去。转移一个球的过程是类似的。每次判断和转移最多不会绕过一圈，所以转移一个球的复杂度为 O(n)，整个算法的复杂度为 O(n2)。正确性不好证明，首先它假设同一个盒子里的球在最终方案里位于连续的一段盒子里，这个性质并不是看起来那么容易证明，不过结合本文中构造的第二个网络流模型也以正出来，即使证明