作者Fenikso (ばかちーは俺の嫁)
看板Prob_Solve
標題Re: [問題] SPOJ 1774. All Discs Considered [ALL]
時間Fri Oct 14 09:24:41 2011
※ 引述《AmosYang (Zzz...)》之銘言：
: 推 Fenikso:模擬一樣是O(D)啊 不會比較慢 10/14 09:03
: 推 Fenikso:我回一篇好了.. 10/14 09:08
: → AmosYang: 能提示一下嗎? :) 10/14 09:08
其實本質上是個dfs XD
1. 先建dependency graph (不是tree 雖然這不太重要XD)
這張圖要用adjacency list存
對每個input (x, y) 從y連一條有向邊到x
同時統計每個點的in degree
到這裡為止是linear
以下假設先放第一片, 放第二片的時候同理
2. 把第一片中in degree是0的點抓出來放到一個array A1,
第二片中in degree是0的點抓出來放到一個array A2,
令i <- 1, 表示現在在光碟機裡面的片子編號
(loop開始)
3. (Ai中所有歌聽過一遍)
loop until Ai is empty:
對所有從點集Ai連出去的邊{(x, y) | x \in Ai} 把y的in degree扣1
如果扣完發現y的in degree降到0, 則把y依編號放入A1或A2
4. (不見了XD)
5. 如果還有歌沒聽過, 則回到3. (換片)
i <- 3 - i
otherwise, break
6. 統計loop的次數就是答案.
因為每條邊只碰到一次, 每個點最多碰到O(degree(v))次
所以整個loop是linear
--
--
※ 發信站 :批踢踢實業坊(ptt.cc)
◆ From: 118.169.226.206
※ 編輯: Fenikso 來自: 118.169.226.206 (10/14 09:25)
※ 編輯: Fenikso 來自: 118.169.226.206 (10/14 09:36)
1F：推 AmosYang: 感謝賜教 :D 10/14 09:33
※ 編輯: Fenikso 來自: 118.169.226.206 (10/14 09:37)
2F：→ AmosYang: 的確，這與我的作法一樣都是 O(D)，但我的作法 10/14 09:48
3F：→ AmosYang: 對 memory 的需求應該會大一些 (用空間換時間) 10/14 09:48
4F：推 AmosYang: 我錯了，我的作法比較慢 (晚了一天才想通 :D) 10/15 11:07