posts - 74, comments - 33, trackbacks - 0

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

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

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

之后進(jìn)行以下步驟。

設(shè)cost為最小樹形圖總權(quán)值。

0.置cost=0。

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

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

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

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

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

3.將有向環(huán)縮成一個點(diǎn)。

假設(shè)環(huán)中的點(diǎn)有（Vk1，Vk2，…?，Vki）總共i個，用縮成的點(diǎn)叫Vk替代，則在壓縮后的圖中，其他所有不在環(huán)中點(diǎn)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的權(quán)值和即為最小樹形圖總權(quán)值。

如要輸出最小樹形圖較煩，沒實(shí)現(xiàn)過。

找環(huán)O(V)，收縮O(E)，總復(fù)雜度O(VE)。

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

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

新加一個點(diǎn)，和每個點(diǎn)連權(quán)相同的邊，這個權(quán)大于原圖所有邊權(quán)的和，這樣這個圖固定跟的最小樹形圖和原圖不固定跟的最小樹形圖就是對應(yīng)的了。

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

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

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



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2025年5月

日

一

二

三

四

五

六

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

2009年3月 (1)

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

Friends

OJ

搜索

最新評論

閱讀排行榜

評論排行榜