Tube's World

Q: http://uva.onlinejudge.org/external/108/10807.html

累死人了這題= =

整整想了2天

跟之前的 UVA 10030 -- Computer Dialogue 一樣

這題的題解除了UVA討論區零零落落的討論之外

根本找不到其他的詳解

只有找到一份用C寫的code, 然後在寫什麼根本看不懂= =

這題難就難在要用MST結合backtrack來找答案

(這題的題目叫Prim, 可是跟Prim完全沒有關係,要用Kruskal才有辦法做)

我的做法是先跑A所有的可能性

只要A建立好一個MST之後

就從剩下的邊開始找,做B的MST

不過因為剩下的邊可能會沒辦法構成一個完整的MST的關係

所以要再檢查B是不是一個MST, 是的話才檢查答案的大小, 最後作印出的動作

剪支是一定要的,不過因為還不熟的關係

我只有判斷說當前的cost如果大於目前的最小值就不要再遞迴下去這樣

然後所有邊中的最小的那個邊

一開始就assign給A

這樣可以減少backtrack的次數

至於為什麼會這樣....大家可以自己想想看^^

( 實際上是因為我不知道該怎麼解釋orz...

簡單來說就是A建立MSTA, B建立MSTB

跟A建立MSTB, B建立MSTA,兩者其實cost是一樣的,所以沒有必要跑全部的情形)

討論區裡其實還有一個更快的想法

只是我用code實作不出來orz

大家可以進去看一下

資料結構是用disjoint set來實作Kruskal跑MST

用backtrack的演算法來跑A的所有可能性

獻給也被這題搞到快瘋掉的夥伴們

這題...還有很大的進步空間啊@@