題目：
如圖，給你一張圖(可能不連通)，然後路上的邊權代表這條路要維修幾天
Q次詢問，每次問你A走到B最少幾天後可以到達
例如圖中A~D點，最快3天可到
做法：
從greedy的想法，我們希望任兩點的路徑都選在愈小的邊愈好
要到達一個點，選取有連接他的邊中權重最小的邊E
而E的另一端也選取連接他的邊中權重最小的邊
一直連，任兩點要有路徑，所以最後會連成一棵樹，而且事實上他就是最小生成樹
於是我們現在知道所求的答案都在樹上
若每次詢問就做一次DFS找路徑上的最大邊，複雜度O(QN)，會超時
這時候可以利用倍增法+LCA
F[i][j]紀錄j的第2^i倍祖先
然後由兩點沿路爬到LCA，順便紀錄走過的邊的最大值
複雜度O(NlogN + QlogN)，分別是建表(F[][])跟詢問
code:
C陣列判斷是否連通
C陣列判斷是否連通
沒有留言:
張貼留言