連結：TOJ207 最小與次小網路建構成本
題目：
保證圖中每條邊權重皆不同，求次小生成樹
做法：
由我們上次求唯一性的結論，邊的權重皆不同，那麼次小就一定是嚴格次小
題目也有提到是嚴格次小，當然的
與昨天那題不同的是，VE範圍又更大了，我們不能做V次MST來找新MST的花費
假設一條樹外的邊E權重=W，其連接的兩個點為u, v
當E替換上來時，拔掉u, v路徑上最大的邊，即是次小的方案
從樹上找兩點路徑上的極值我們以前曾經做過！TIOJ1163 施工中的道路
用倍增法LCA維護，建表複雜度O(VlogV)，每次查詢只需O(logV)時間！
那麼把樹外的每一條邊都試試看，找出所有嘗試過的次小方案中最小的那個。
複雜度約是O(ElogE + VlogV + ElogV)，分別是MST、建表、嘗試每條樹外的邊
code:
沒有留言:
張貼留言