posts - 74, comments - 33, trackbacks - 0

對于最小樹形圖前幾天做了n個不定根的最小樹形圖，因為n<16對此我用的是dp方法WS過去了那道題目，0.3s相對于最小樹形圖的正確解法的0.001實在是慚愧，為此也找到了一種最小樹形圖的DP解法當然n<16時間和空間上才能受得了。
再談朱劉算法解決最小樹形圖問題：下面是轉載的資料：

有固定根的最小樹形圖求法O(VE)：

首先消除自環，顯然自環不在最小樹形圖中。然后判定是否存在最小樹形圖，以根為起點DFS一遍即可。

之后進行以下步驟。

設cost為最小樹形圖總權值。

0.置cost=0。

1.求最短弧集合Ao?（一條弧就是一條有向邊）

除源點外，為所有其他節點Vi，找到一條以Vi為終點的邊，把它加入到集合Ao中。

（加邊的方法：所有點到Vi的邊中權值最小的邊即為該加入的邊，記prev[vi]為該邊的起點，mincost[vi]為該邊的權值）

2.檢查Ao中的邊是否會形成有向圈，有則到步驟3，無則到步驟4。

（判斷方法：利用prev數組，枚舉為檢查過的點作為搜索的起點，做類似DFS的操作）

3.將有向環縮成一個點。

假設環中的點有（Vk1，Vk2，…?，Vki）總共i個，用縮成的點叫Vk替代，則在壓縮后的圖中，其他所有不在環中點v到Vk的距離定義如下：

gh[v][Vk]=min?{?gh[v][Vkj]-mincost[Vkj]?}?(1<=j<=i)而Vk到v的距離為

gh[Vk][v]=min?{?gh[Vkj][v]?}??????????????(1<=j<=i)

同時注意更新prev[v]的值，即if(prev[v]==Vkj)?prev[v]=Vk

另外cost=cost+mincost[Vkj]?(1<=j<=i)

到步驟1.

4.cost加上Ao的權值和即為最小樹形圖總權值。

如要輸出最小樹形圖較煩，沒實現過。

找環O(V)，收縮O(E)，總復雜度O(VE)。

那幅對我有莫大幫助的流程圖如下，

對于不固定根的最小樹形圖，wy教主有一巧妙方法。摘錄如下：

新加一個點，和每個點連權相同的邊，這個權大于原圖所有邊權的和，這樣這個圖固定跟的最小樹形圖和原圖不固定跟的最小樹形圖就是對應的了。

這分資料上在理論上證明并不完整導致看上去也許多不解之處.......而具體證明建議是自己按照資料上說的出幾個帶環的圖然后按照上面說一布一步執行慢慢的就會理解證明,
對于實現代碼建議自己先寫一份然后搜一份模板比對一下。

posted on 2009-04-30 17:16 KNIGHT 閱讀(1315) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2009年5月

日

一

二

三

四

五

六

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

2009年3月 (1)

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

Friends

OJ

搜索

最新評論

閱讀排行榜

評論排行榜