Re: [問題] SPOJ 1774. All Discs Considered [ALL]
看板Prob_Solve (計算數學 Problem Solving)作者Fenikso (ばかちーは俺の嫁)時間13年前 (2011/10/14 09:24)推噓2(2推 0噓 2→)留言4則, 1人參與討論串2/3 (看更多)
※ 引述《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)
推
10/14 09:33, , 1F
10/14 09:33, 1F
※ 編輯: Fenikso 來自: 118.169.226.206 (10/14 09:37)
→
10/14 09:48, , 2F
10/14 09:48, 2F
→
10/14 09:48, , 3F
10/14 09:48, 3F
推
10/15 11:07, , 4F
10/15 11:07, 4F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12