國家集訓隊作業(yè)0090deliveries

1、IOI2003 中國國家集訓隊難題活動0090 解題長沙學校【題目大意】一棟有 10 層樓?，F(xiàn)有 k 個第 tk 層去。，第 k 個在第 sk 層，要求被運送到只有一個運貨員運送這些，并且他在同一時刻至多只能拿一個。他從 1 層出發(fā)并且最后回到 1 層。問：他最少要上多少層樓才能把所有的運送到位？【解決情況】問題已經(jīng)完全解決，采用的是構(gòu)造圖、然后求回路的算法。算法時間復(fù)雜度為 O(k)，空間復(fù)雜度為 O(n+k)?！舅惴ü８拧看祟}問的是最少上樓層數(shù)，然而發(fā)現(xiàn)：由于運貨員要從第一層出發(fā)并且最終返回第一層，所以只要上了一層樓就必定對應(yīng)的要下一層樓。于是問題可以轉(zhuǎn)化為求總上下樓層數(shù)最少。把每層樓看作

2、一個頂點，將上下樓這樣的活動看作邊，構(gòu)圖。然后進行適當?shù)男薷?，添加最少的邊得到一個圖；最后通過求回路來構(gòu)造解。【收獲與感謝】感謝啟明對我在此題上的幫助?！菊摹靠紤]現(xiàn)在如果有一個X 在 3 樓，要運到 5 樓去。運貨員必然要在某一步把 X 從 3 樓運到 4 樓，然后也許轉(zhuǎn)而去運送其他的包裹；最后再返回 4 樓來把 X 從 4 樓運到 5 樓。這個運貨員拿著 X 經(jīng)過了 34, 45 這樣兩個上樓過程。盡管這兩個過程不一定是連在一起進行的，但“拿著 X 從 3 樓上到 4 樓”以及“拿著 X 從 4 樓上到 5 樓”這兩個事件遲早都要發(fā)生。如果把每一層樓看作一個頂點，上樓、下樓的事件看作邊的話

3、，對于上面的例子，就可以連兩條有向邊：34，45。的例子：要從 6 樓運送到 2 樓，則連邊：65, 54, 43, 32。要從 1 樓運送到 4 樓，則連邊：12, 23, 34。存在存在可以構(gòu)出一個圖 G1。按照以上規(guī)則，根據(jù)輸入數(shù)據(jù)G1 中的每條邊代表一個事件，這些都是必須事件，無論如何都要發(fā)生的，必不可少。注意到題目要求：從一樓出發(fā)最后回到一樓。也就是運貨員每上一層樓，就對應(yīng)著要下一層樓。比如他某一時刻從 34，那么在之后的某個時候他肯定要從 43；不然怎么回 1 樓呢！這個規(guī)律稱之為“上下樓平衡原則”。也就是說 34 這樣的弧的數(shù)目，應(yīng)該等于 43 這樣的弧的數(shù)目！一般的假設(shè) ii+

4、1 有 p 條弧，i+1i 有 q 條弧，則：1、pq。增加 p-q 條 i+1i 的弧。2、pq。增加 q-p 條 ii+1 的弧。進行如此修改之后的圖稱之為 G2。很顯然 G2 中的邊也都是必不可少的邊。進一步一個例子：一個，s1=3, t1=4。第一層（虛線表示是后來添加的邊）運貨員必須從第一層出發(fā)，而發(fā)現(xiàn) 3、4 兩個點和 1 實際上是分開的它們并不連通！從一樓出發(fā)運貨員遲早是要通過 34 的，為了達到這個目的，必然要先經(jīng)過 12, 23；同時為了保持上下樓平衡，還要添加 32, 21。一般的， 把 ii+1, i+1i 的所有邊統(tǒng)稱為“i 樓道邊”。如果存在“j 樓道邊”，而不存在“

5、i 樓道邊”（ij），那么顯然就要添加 ii+1 和 i+1i 這兩條邊。（因為從 1 出發(fā)要到達 j 必然途徑 i，因此 i 樓道至少要有一條邊）這樣添加之后就能保證所有的邊都在通過以上的諸多規(guī)則，通分量里面構(gòu)造出一個全新的圖 G=(V,E)，|V|=10，|E|2k。根據(jù)就是的構(gòu)造規(guī)則，很容易發(fā)現(xiàn) G 中的邊都是必須邊，的下界。然而這個下界能不能達到呢？。因此|E|/2先來看看 G1、G 的所有邊在性質(zhì)：同分量里面。2、G 中每個點的出度等和入度相等。（根據(jù)上下樓平衡原則可知）也就是說 G 是一個圖！這樣就可以把它“一筆畫”，也就是不重復(fù)的遍歷所有的邊！這樣一種遍歷順序（也就是一條貨的順序

6、，這個下界是可以達到的！慢著不要激動得太早。究竟能不能達到回路）實際上就是一種送繼續(xù)分析。首先介紹一下回路的求法。從 s 點出發(fā)（s 是出發(fā)點），任意求一個回路C，并且在原圖中將 C 中的邊刪除。如果發(fā)現(xiàn)回某一點 p 的度不為 0，就再從 p 出發(fā)任意求一條回路 C，并且將 C從 p 的位置（也就是 CC+C）；刪除 C中的邊。C 中，形成新的 C 回路繼續(xù)檢查 C 中的點，如果還存在 p 的度不為 0，則從 p 出發(fā)求一個回路如是反復(fù)，直到 C 中所有點的度都為 0。此時的 C 就使一個回路了。以上算法要從 p 點出發(fā)求一條回路，這條回的邊是沒有任何限制的。然12, 23。在遍歷 23 之前

7、，必而本題的邊卻有一定的限制。比如一個須先遍歷 12，否則還在 1 樓，你運什么上 3 樓?。≌捎谶呌幸欢ǖ捻樞蛞?，所以此題又不是簡單的回路。解決方法是“一走到底”。也就是說我求“從 p 出發(fā)的一條回路”的時候，一旦開始送某個，那么我中途就不去抽空管其他的，先把這個的相關(guān)路徑全部走完再說。這樣就能保證遍歷邊的順序性。也就是說回路是可以求出來的，下界也是可以達到！問題也就解決了。來回顧一下算法：1、根據(jù)輸入數(shù)據(jù)構(gòu)圖。2、根據(jù)“上下樓平衡原則”添邊。3、為保持“圖的連通性”添邊。4、“一走到底”求5、輸出。回路。以上就是算法的全部內(nèi)容，時間復(fù)雜度 O(k)，空間復(fù)雜度 O(n+k)。由于 n=10， k=50，所以速度非?？?。實際上完全可以把 n 和 k 的范圍大大的擴大?！具M一步研究的方向】1、增加人數(shù)。增加人數(shù)之后如果要求總上樓數(shù)最少，可以發(fā)現(xiàn)就是無論