集訓隊作業(yè)boxes解題報告

1、IOI2003 中國國家集訓隊難題活動0018Boxes解題省蕪湖市第一中學【題目大意】給出 N 個排成一圈的盒子，依次順時針為 1,2,N，每個盒子 i 有且僅有一個順時針方向上的鄰居 i+1(若 i=N 則為 1)和一個逆時針方向上的鄰居 i-1(若 i=1 則為 N)。第 i 號盒子中初始時已經(jīng)擺放了 Bi 個球，每一步可以把某一個球從原先所在的盒子移動到這個盒子的順時針或逆時針鄰居內(nèi)?，F(xiàn)要使所有的盒子里面最多只有一個球，求最少需要移動多少步。題目保證所有的球的總數(shù) M 不超過 N(否則顯然無解)?！窘鉀Q情況】采用最小費用流求解，時間復雜度為 O(kMN)，其中 k 為一個不確定的系數(shù)，

2、通常 k 可以看作一個不太大的常數(shù)，因此時間復雜度可看成 O(N2)?？臻g復雜度為 O(N)?！舅惴ü８拧繕?gòu)造出合適的網(wǎng)絡(luò)流的模型，使每個流對應著一個球以及它最終所在的盒子，同時這個流上的總費用對應著這個球移動的步數(shù)，構(gòu)造出的網(wǎng)絡(luò)圖滿足 O(E)=O(V)。最后就是要求總費用最小，總流量為 M 的一個流，因此需要從 0 流擴展 M 次，每次首先采用 SPFA算法找一條費用最小的增廣路徑，復雜度為 O(kN)，再用這個增廣路徑擴展可行流，復雜度為 O(N)，所以總的時間復雜度為 O(kMN)。【正文】看了題目，可以有兩種思路：第一種是動態(tài)規(guī)劃，目前已知的最好方法似乎只是O(n3)的，比較不能接受

3、。第二種是最佳匹配或者最小費用流，也就是本文將算法。匹配或流的是很自然的：最終每個球都必須在某個盒子內(nèi)，但每個盒子最多只能放一個球，球原來所在的位置到最終的位置的距離就是這個球轉(zhuǎn)移的最小步數(shù)。所以很容易想到：以球為點集 A，盒子為點集 B，每個盒子 i 中所有的到每個盒子 j 都有一條邊，權(quán)值就是盒子 i 到 j 的最短距離(順時針距離和逆時針距離的最小值)。這樣建立的就是一個二部圖的模型。例如對于 5 個盒子 1,2,3,4,5，其中擺放的球分別有 0,1,0,2,1 個，則建立出的是如下的一個圖：15圖中的圓圈代表球，從左到右分別是 2 號盒子,4 號盒子,4 號盒子以及 5 號盒子內(nèi)的球

4、。方格代表盒子，方格內(nèi)的數(shù)字是盒子的。每個球到每個盒子都有邊，邊上的數(shù)字代表其權(quán)值，也就是球原先所在的格子到邊所連的格子的最短距離，沒有標數(shù)字的邊是一條權(quán)值為 0 的邊。很顯然，在這個二部圖中求使所有匹配邊權(quán)值和最小的一個最佳匹配，其最小權(quán)值和就是要求的 。又或者 把原來在同一個盒子中的球并到一個結(jié)點，添加一個源 S 和一個匯 T，用 S到每個 A 類點的邊的容量代表同一個盒子中原先有球的總數(shù)，費用為 0。每個 A 類點到每個 B 類點有一條容量為 1 的邊，代表最終可以把一個球轉(zhuǎn)移到邊所連的盒子內(nèi)，邊的費用為起點代表的球到終點所代表的盒子的最短距離。每個 B 類點到 T 有一條容量為 1，費

5、用為0 的邊，代表每個盒子最多可以放一個球。例如同樣是上面的例子，可以建立下圖：S21111T圖中 S 到圓圈的邊上的數(shù)字代表容量，除了 S 到圓圈的邊，其它邊的容量均為 1。圓圈到方格的邊上的數(shù)字代表費用，也就是轉(zhuǎn)移的最少步數(shù)，未標出數(shù)字的費用為 0，除了圓圈到方格的邊，其它邊的費用均為 0。不難看出，在這個圖里求從 S 到 T 的最小費用最大流，求出的最小費用就是要求的。以上兩種方法的本質(zhì)都是相同的：直接建立每個有球的位置到所有盒子的關(guān)系，因此建立出的都是二部圖的形式，并且每個 A 類點到每個 B 類點都有邊。在這種圖內(nèi)無論是求最佳匹配還是求最小費用最大流，其復雜度都是 O(MVE)級別，

6、其中 M 是球數(shù)，V 是頂點數(shù)，它們的規(guī)模都是 O(N)，E 是邊數(shù)，規(guī)模為 O(N2)，因此整個復雜度高達 O(n4)，顯然是不可接受的。以上建立的圖論模型之處在于它不能很好地體現(xiàn)出轉(zhuǎn)移的連續(xù)性，也就是一個球轉(zhuǎn)移到離原來的盒子距離為 d+1 的盒子之前，它一定先轉(zhuǎn)移到了距離為 d 的盒子內(nèi)，而轉(zhuǎn)移到距離為 d+1 的盒子內(nèi)的費用是轉(zhuǎn)移到距離為 d 的盒子內(nèi)的費用加 1。為了體現(xiàn)這種特性，建立第二個網(wǎng)絡(luò)流模型：設(shè)一個源 S 和一個匯 T。每個盒子對應一個頂點，如果一個盒子 I 有 b 個球，那么就連有向邊 S-I，容量為 b，費用為 0，一個S-I 的流就代表盒子 I 中的一個球。對每個盒子

7、I 都連一條有向邊 I-T，容量為 1，費用為 0，一個 I-T 的流就代表最終有一個球轉(zhuǎn)移到了盒子 I 并定下來。每個盒子 I 項它的順時針鄰居 J 連一條有向邊 I-J，容量為無限，費用為 1，代表轉(zhuǎn)移到了盒子 I 的球可以5向 J 轉(zhuǎn)移，花費一步。同理，每個盒子 I 向它的逆時針鄰居 H 連一條有向邊 I-H，代表轉(zhuǎn)移到了盒子 I 的球可以向 H 轉(zhuǎn)移，花費一步。同樣對于開頭下的模型：例子，可以建立如S211T圖中 S 到方格的邊上的數(shù)字表示容量，費用均為 0。方格之間的邊容量均為無限，費用均為 1。方格到 T 的邊容量均為 1，費用均為 0。不難看出，在這樣構(gòu)造出的圖中求 S 到 T

8、的最小費用最大流，求出的最小費用也就是所要求的最少移動步數(shù)。建立的第二個網(wǎng)絡(luò)流模型最多只有 4N 條邊，因為方格點之間有 2N 條邊，方格點到 T 有 N 條邊，S 到方格點最多只有 N 條邊。也就是說，這個模型中 O(E)=O(V)=O(N)。這是一個很 Sharp 的性質(zhì)，下面將會看到它起了的作用。對建立起來的網(wǎng)絡(luò)圖求最小費用最大流，如果采用所謂“先流推進”(PreFlow_Push)方法的話，似乎是 O(sqrt(E)*V)級的，但是作者不是很清楚這種方法，所以典的求增廣路徑的方法。每次在當前的圖中找一條費用最小的增廣路徑，實際上就是以 S 為源點，把當前圖中每條未滿邊看作距離等于費用的

9、邊，把每條有流量的邊看作距離為費用相反數(shù)的邊，求 S到T 的最短路。由于可能出現(xiàn)負邊，所以要采用迭代法來求這個最短路。如果用 Bellman_Ford來實現(xiàn)迭代，則每次求最短路的復雜度為 O(VE)=O(N2)，而根據(jù)求出的增廣路徑擴展可行流的復雜度為 O(N)。最大的流量肯定是 M，所以總的復雜度為 O(MN2)=O(N3)。理論上比較高，但實際往往很難達到 情況，因此效果還是比完全 O(N3)的動態(tài)規(guī)劃要好的。采取更有效的迭代方法來求增廣路徑(也就是最短路)，即所謂 SPFAShortest Path Faster Algorithm，它可以在 O(kE)的時間復雜度內(nèi)求出源點到其他所有點

10、的最短路徑，可以處理負邊。SPFA 的實現(xiàn)甚至比 Dijkstra 或者 Bellman_Ford 還要簡單：設(shè) DistI代表 S 到 I 點的當前最短距離，F(xiàn)aI代表 S 到 I 的當前最短路徑中 I 點之前的一個點的 。開始時 Dist 全部為+，只有 DistS=0，F(xiàn)a 全部為 0。一個隊列，里面存放所有需要進行迭代的點。初始時隊列中只有一個點 S。用一個還是采用經(jīng)數(shù)組每個點是否處在隊列中。每次迭代，取出隊頭的點 v，依次枚舉從 v 出發(fā)的邊 v-u，設(shè)邊的長度為 len，判斷 Distv+len 是否小于 Distu，若小于則改進 Distu，將 Fau記為 v，并且由于 S 到

11、u 的最短距離變小了，有可能 u 可以改進其它的點，所以若 u 不在隊列中，就將它放入隊尾。這樣一直迭代下去直到隊列變空，也就是 S 到所有的最短距離都確定下來，結(jié)束算法。SPFA 在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個點出了隊列就51432不可能重新進入隊列，但是 SPFA 中一個點可能在出隊列之后再次被放入隊列，也就是一個點改進過其它的點之后，過了一段時間可能本身被改進，于是再次用來改進其它的點，這樣反復迭代下去。設(shè)一個點用來作為迭代點對其它點進行改進的平均次數(shù)為 k，有辦法證明對于通常的情況，k 在 2 左右(怎么證明的作者也不知道)。由于所有的點分別作一次迭代點進行

12、改進的復雜度為 O(E)，所以整個算法的復雜度為 O(kE)=O(E)。注意到這里又有一個看似不正確的地方k 是所有點作迭代點的平均次數(shù)，而每個點的邊數(shù)是可能不同的，如果邊比較多的點作迭代點的次數(shù)很多的話，復雜度應該就不止 O(kE)了，但是似乎又可以證明不會出現(xiàn)的情況，不過本題中出了 S 之外，所有的點都只有常數(shù)條邊，而 S 顯然不會多次迭代，所以不需要考慮這個問題?？傊琒PFA 理論上的復雜度為 O(kE)，而作者對于本題的數(shù)據(jù)進試，發(fā)現(xiàn)對大部分數(shù)據(jù)，k 都小于 1！只有極少數(shù)的數(shù)據(jù)中 k 達到了 1，沒有超過 1 的，也許這可以從本題的圖的特殊性質(zhì)證明吧。用 SPFA 可以在 O(kE

13、)的時間復雜度內(nèi)求出最短路（也就是增廣路徑），用增廣路徑來擴展可行流的時間復雜度為 O(V)，而這里 O(E)=O(V)=O(N)，所以可行流擴展一次的時間復雜度為 O(kN)，而可行流擴展 M 次之后達到最大，因此整個算法的時間復雜度為 O(kMN)，可以看成 O(N2)，非常好了?？臻g復雜度可以控制在 O(N)，因為除 S 外，每個點出發(fā)的邊為常數(shù)，而從 S 出發(fā)到每個點最多只有一條邊，存整個圖的復雜度可以做到 O(N)，而 SPFA 中用到的 Dist,Fa 以及布爾數(shù)組都是 O(V)規(guī)模的，只有一個隊列不好估計應該開多長，但是沒有關(guān)系，因為任意時刻隊列中不會有兩個相同點，因此如果用循環(huán)

14、隊列來實現(xiàn)，只需要長度為 N 的數(shù)組就可以了。在解決本題的過程中，根據(jù)先構(gòu)造了本質(zhì)相同的一個匹配和一個網(wǎng)絡(luò)流模型，但是發(fā)現(xiàn)這兩個模型不能充分利用到題目的條件，使算法的復雜度太高，所以構(gòu)造了第二個網(wǎng)絡(luò)流的模型，很好地切合了題目的本質(zhì)，使得構(gòu)造出的圖邊數(shù)與點數(shù)同階，然后了 SPFA 方法求最短路，最終把時間復雜度做到了實際意義上的 O(N2)。采用可見，構(gòu)造模型要盡量精確，盡可能利用到題目中的條件。對同一個模型，要選擇合適的算法去求解它。本題程序見 kul.pas?！具M一步研究的方向】1.2.可以考慮用 PreFlow_Push 方法來求最小費用最大流，這樣復雜度又可以降低。標準是這樣的：數(shù)組it

15、ion1.n非零的格子的位置，Rest1.n對應的非零的格子的小球數(shù)減。ClockWise1.n每個非零格子需要順時針轉(zhuǎn)移的最遠的位置，lockWise1.n每個非零格子需要逆時針轉(zhuǎn)移的最遠的位置ition 和 Rest 根據(jù)輸入確定，ClockWise和lockWise 開始都等于ition，也就是原來所在的位置。依次處理每一個點 i，如果Resti0，就算出這個點順時針和逆時針轉(zhuǎn)移一個球的 Cost，選擇較小的一個，轉(zhuǎn)移。計算Cost 的方法，順時針和逆時針是對稱的，以順時針為例：假設(shè)順時針地轉(zhuǎn)移，那么會導致 ClockWisei改為順時針的下一個（相應地，要增加一定的轉(zhuǎn)移步數(shù)），然后判斷l(xiāng)ockWisej是否等于 ClockWisei，其中 j 為 i 的順時針的下一個非零格，若等于，則lockWisej改為順時針的下一個，同時 ClockWisej改為順時針的下一個，并更改 Cost中的轉(zhuǎn)移步數(shù)。這樣，等于是 j 又向順時針轉(zhuǎn)移了一個，可能會造成連鎖的反應，所以要繼續(xù)判斷下去。轉(zhuǎn)移一個球的過程是類似的。每次判斷和轉(zhuǎn)移最多不會繞過一圈，所以轉(zhuǎn)移一個球的復雜度為 O(n)，整個算法的復雜度為 O(n2)。正確性不好證明，首先它假設(shè)同一個盒子里的球在最終方案里位于連續(xù)的一段盒子里，這個性質(zhì)并不是看起來那么容易證明，不過結(jié)合本文中構(gòu)造的第二個網(wǎng)絡(luò)流模型也以正出來，即使證明