×
解除綁定,重新設定系統帳號的密碼
您的系統帳號 ID:
您的系統帳號:
您的帳號暱稱:
設定新密碼:
設定新密碼:
×
請輸入要加入的「課程代碼」
請向開設課程的使用者索取「課程代碼」
分類題庫
解題動態
排行榜
討論區
競賽區
登入
註冊
發表新討論
#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