posts - 74, comments - 33, trackbacks - 0

對于最小樹形圖前幾天做了n個(gè)不定根的最小樹形圖，因?yàn)閚<16對此我用的是dp方法WS過去了那道題目，0.3s相對于最小樹形圖的正確解法的0.001實(shí)在是慚愧，為此也找到了一種最小樹形圖的DP解法當(dāng)然n<16時(shí)間和空間上才能受得了。
再談朱劉算法解決最小樹形圖問題：下面是轉(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中的邊是否會(huì)形成有向圈，有則到步驟3，無則到步驟4。

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

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

假設(shè)環(huán)中的點(diǎn)有（Vk1，Vk2，…?，Vki）總共i個(gè)，用縮成的點(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)

同時(shí)注意更新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教主有一巧妙方法。摘錄如下：

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

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

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

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



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

2009年3月

日

一

二

三

四

五

六

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

2009年3月 (1)

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

Friends

OJ

搜索

最新評論

閱讀排行榜

評論排行榜