推 A4P8T6X9:dijkstra每一步驟都是拿最小點，在把周圍的點可以走到的 01/07 18:24
→ A4P8T6X9:點更新距離，拿一次最小點是logn，而用fib的話更新距離只 01/07 18:24
→ A4P8T6X9:要O(1)，點要拿n次，而邊最多更新E次，所以是E+vlogv。 01/07 18:24
→ WashFreeID:thx 懂了 01/07 18:27
https://dl.dropboxusercontent.com/u/14571319/2014-01-07%2018.19.43.jpg
想法跟洪捷不一樣
不知道對不對
step 1:
讀line 2 -n
v-1個邊
step 2:
設一個集合 A=V
只要每個讀入得邊有出現過的頂點就刪掉
如果每個點都出現過
就是樹
因為樹是最小連接所有點的acylic
如果有點沒有出現在任何邊 就是unconnected
這樣對嗎
順便問
Djkstra's 用Fibonacci Heap O(E+VlgV)
Edmonds Karp O(V*E^2)
怎推的？
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.255.18.138