#16470:


freedom501999@gmail.com (帥氣魔方生)

學校 : 不指定學校
編號 : 88611
來源 : [39.8.203.54]
最後登入時間 :
2019-05-30 22:56:25
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [27.52.77.116] | 發表日期 : 2019-01-04 09:20

這題測資最多十萬,所以接下來說的陣列都必須放在全域,而且每個陣列都要 100001 個元素,第 0 個不用到

為了記錄整張圖,一般會想到用 Linked List,但是測資太多, heap 肯定不夠

觀察題目可以發現,所有節點 (根 除外) 都恰有一個父節點,於是可以宣告一個陣列來存整張圖

A[ child ]= node,代表 節點 child 的父節點是 node

同時要用另一個陣列記錄該節點的子節點,就是每行的第一個數字

接著就是要處理每個點的高度,用DFS 會因為測資太大而 TLE,必須用其他方法

這裡有一個很妙的方法,利用 "佇列" ( 以陣列實現 )

在讀取每個點的資料時,如果第一個數字是 0,代表此點是葉節點,就丟進佇列

讀完所有資料後就開始處理,從葉子開始,往上直到根為止

每次從佇列拿出一個點 child,找 child 的父節點 node 比較其高度

( 每個節點的高度,一樣用陣列存 )

node 的高度更新為:( node 原高度 ) 與 ( child 高度 +1 ) 中較大者

之後 node 的子節點數量減一,只要 node 的子節點數變成 0,node 本身變成目前的樹的葉節點,就把 node 丟進佇列

重複上述步驟,拿出佇列、處理、更新節點高度,直到把所有節點 ( 包含根 ) 的高度都更新完

最後加總高度,印出根及總高度即是答案

PS:總長度在最後一筆測資會超過 int 大小,要改用 long long int 存

 
ZeroJudge Forum