1、An efficient algorithm for the length-constrainedheaviest path problem on a tree湖南沙郡中學(xué)源An efficient algorithm for the length-constrained heaviest path problem on atreeBang Ye Wu, Kun-Mao Chao, Chuan Yi Tang一、摘要給定一棵樹(shù)，樹(shù)的每條邊都值和長(zhǎng)度。要求在樹(shù)中找出一個(gè)路徑，路徑的長(zhǎng)度不大于給定的長(zhǎng)度，且路徑上的邊權(quán)和最大。An efficient algorithm for the lengt

2、h-constrained heaviest path problem on a tree找出了一個(gè) O(nlg2n)的方法解決此問(wèn)題，并且：當(dāng)邊權(quán)的范圍為 O(n)時(shí)復(fù)雜度可降到 O(nlgn)。同時(shí)，論：1、在給定路徑長(zhǎng)度上限時(shí)求邊權(quán)和最小的路文還解決了另外三個(gè)類(lèi)似徑；2、在給定路徑長(zhǎng)度下限時(shí)求邊權(quán)和最大的路徑；3、在給定路徑長(zhǎng)度下限時(shí)求邊權(quán)和最小的路徑。說(shuō)明：在開(kāi)始這篇文章前中的簡(jiǎn)單路徑(即最短路)。假設(shè)讀者熟悉樹(shù)的最基本概念，理解樹(shù)二、問(wèn)題描述設(shè) T=(V,E)是一棵樹(shù)，其中 V 是它的頂點(diǎn)集，E 是它的邊集。w,l 分別為每條邊的邊權(quán)和長(zhǎng)度函數(shù)。令 P=（PV,PE）=Path(u,

3、v)表示 u 和 v 之間唯一的簡(jiǎn)單路徑，并定義： 第二步：選定一個(gè)結(jié)點(diǎn) m 為根結(jié)點(diǎn)，令 si 表示 m 的兒子結(jié)點(diǎn)。第三步：對(duì)于樹(shù)中的每個(gè)結(jié)點(diǎn) v，計(jì)算：Xv.length=l(Path(m,v)，即根 m 至 v 的路徑長(zhǎng)度；Xv.weight=th(m,v)，即根 m 至 v 的路徑的邊權(quán)和；Xv.subtree=j(若v Ts )，即 v 是 m 的哪個(gè)兒子或哪個(gè)兒子的子孫。j第四步：計(jì)算一個(gè)端點(diǎn)在 m 的路徑中的最優(yōu)解，設(shè)為 hweight，即： hweight(m)=maxXv.weight|Xv.lengthB hweight(m).p1=mhweight(m).p2=v(Xv

4、.lengthB 且 Xv.weight=hweight(m)第五步：令 qi表示所有結(jié)點(diǎn)中到根的長(zhǎng)度第 i 短的結(jié)點(diǎn)的Xqi.lengthXqi+1.length。第六步： 令 mui 表示到根的距離前 i 短的的結(jié)點(diǎn)中權(quán)值最大的結(jié)點(diǎn)， pm1i=Xmui.weight，f1i=Xmui.subtree；mvi表示表示到根的距。即使得：離前i 短的的結(jié)點(diǎn)中除Xmui.subtree外中的結(jié)點(diǎn)外權(quán)值最大的結(jié)點(diǎn)，pm2i=Xmvi.weight，f2i=Xmvi.subtree。若令 pm2i=-，f2i=-1。第七步：找出邊權(quán)最大的結(jié)點(diǎn)對(duì)：for i1 to n do找出最大的 j，使 Xqj

5、.length+Xqi.lengthB若 j 不存在則進(jìn)入下一步mvi不存在，則若 f1j=Xqi.subtree，則 tmpMaxXqi.weight+pm2j, tmpMax_p1qi,tmpMax_p2mvj； 否 則tmpMaxXqi.weight+pm1j,tmpMax_p1 qi, tmpMax_P2muj；若tmpMax優(yōu) 于hweight(m) ， 即tmpMaxhweight(m) ， 則hweight(m)tmpMax; hweight(m).p2tmpMax_p2; endforhweight(m).p1tmpMax_p1;第八步：計(jì)算 m的最優(yōu)解。最 終 結(jié) 果 ： h

6、weight=maxhweight(i) ， bestroot=i (hweight(i)=hweight) ， hweight.p1=hweight(bestroot).p1，hweight.p2=hweight(bestroot).p2。hweight為最大權(quán)，hweight.p1 和 hweight.p2 為最大權(quán)路徑的兩個(gè)端點(diǎn)。3.3 細(xì)節(jié)處理此處的選擇并不是隨意選擇，而要選擇一個(gè)點(diǎn)，使它的每棵的結(jié)點(diǎn)數(shù)不超過(guò)總結(jié)點(diǎn)數(shù)的一半，這樣才能使復(fù)雜度為預(yù)期的復(fù)雜度。實(shí)現(xiàn)這個(gè)有多種方法，下面其中的一種：令 x 為一個(gè)臨時(shí)根。從樹(shù)的葉子結(jié)點(diǎn)計(jì)算以每個(gè)結(jié)點(diǎn)為根的的結(jié)點(diǎn)數(shù)，令第 i 個(gè)結(jié)點(diǎn)的的結(jié)點(diǎn)數(shù)為

7、Ti，找到出現(xiàn)的第一個(gè)滿(mǎn)足|Ti|超過(guò)總結(jié)點(diǎn)數(shù)/2 的結(jié)點(diǎn)。則這個(gè)結(jié)點(diǎn)滿(mǎn)足條件，設(shè)它為 m。此處的可從根開(kāi)始做一個(gè)深度優(yōu)先或廣度優(yōu)先遍歷。則：1)若 v 是 m 的兒子X(jué)v.length=l(m,v);Xv.weight= w(m,v);Xv.subtree=v2)若 v 不是 m 的兒子，設(shè) parv 為 v 的父結(jié)點(diǎn)Xv.length=l(parv,v)+Xparv.length;Xv.weight=rv,v) +Xparv.weight;Xv.subtree=Xparv.subtree;此處可以直接使用快速排序，其時(shí)間復(fù)雜度為 O(nlgn)，若所有的邊權(quán)為 O(n)，則可用基數(shù)排序，其

8、時(shí)間復(fù)雜度為 O(n)。此處的 mui，mvi都可以由 mui-1及 mvi-1得到，具體過(guò)程如下：1)mu1=1,mv1=-1for i2 to n do若 Xqi.weightXmui-1.weight 則3.11)muiqi3.12) 若 Xmui-1.subtree=Xqi.subtree mvimui-1否則3.21)muimui-1則mvimvi-1 否 則3.22) 若 (Xqi.subtree Xmui.subtree)and(mvi-1=-1)or(Xqi.weightXmvi-1.weight)則 mvi qi否則 mvimvi-1 4)endfor此處，當(dāng) i 遞增時(shí)，j

9、 是遞減的，因此，只要設(shè)置一個(gè)指針從大往小滑動(dòng)即可。當(dāng) j1 時(shí)，即 j 不存在。四、拓展1、在給定路徑長(zhǎng)度上限時(shí)求邊權(quán)和最小的路徑：在輸入后將 w(e)變?yōu)?w(e)即可。2、在給定路徑長(zhǎng)度下限時(shí)求邊權(quán)和最大的路徑：在輸入后將 B 變?yōu)?B，l(e)變?yōu)?l(e)即可。3、在給定路徑長(zhǎng)度下限時(shí)求邊權(quán)和最小的路徑：在輸入后將 B 變?yōu)?B，l(e)變?yōu)?l(e)，w(e)變?yōu)?w(e)即可。五、總結(jié)5.1 算法的主要 本算法的主要就是，先處理特殊情況有一個(gè)路徑經(jīng)過(guò)根結(jié)點(diǎn)，然后對(duì)于不是這種特殊情況的，將它分解到中進(jìn)行處理。這是典型的遞歸。這使用這種時(shí)，一個(gè)重要就是如何使得復(fù)雜度不至于太高，在這個(gè)

10、算結(jié)點(diǎn)相對(duì)平均，這里的平均，并不是別的很法中，使用了一種技巧：使根的復(fù)雜的平均，而是簡(jiǎn)單的使結(jié)點(diǎn)數(shù)最多的的結(jié)點(diǎn)數(shù)不超過(guò)整棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)的一半，這樣的好處，就是保證了遞歸的層數(shù)不會(huì)超過(guò) lg n 層。顯然一個(gè)結(jié)點(diǎn)在每一層都至多被處理一次，所以保證了復(fù)雜度較低。5.2 算法使用的一些技巧：1)選定結(jié)點(diǎn)：選根結(jié)點(diǎn)是此算法中一個(gè)很值得借見(jiàn)的。其實(shí)不選根結(jié)點(diǎn)算法也可以正確結(jié)束，但算法復(fù)雜度將變?yōu)?O(n2lgn)，正是根結(jié)點(diǎn)的巧妙選取，使得算法更好的解決。2)多處采用了已知的結(jié)果：如第三步，第六步，第七步等。六、源程序program An_efficient_algorithm_for_the_leng

11、th_constrained_heaviest_pa th_problem_on_a_tree;/ An em/標(biāo)題：efficient algorithm for the length-constrained heaviest path probl on a tree時(shí)間復(fù)雜度：O(n lg2 n)空間復(fù)雜度：O(n)作者：學(xué)校：湖南沙郡中學(xué)指導(dǎo)老師：向期中 日期：2005-04-24說(shuō)明：1.本程序只解決了邊長(zhǎng)與邊權(quán)為整數(shù)的情況，若其為實(shí)數(shù)，只要將相應(yīng)的類(lèi)型更改即可。2.本程序所解決一樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多為 100，當(dāng)要求結(jié)點(diǎn)個(gè)數(shù)應(yīng)的值即可。時(shí)，只要將 maxn 改為相因?yàn)楸境绦驗(yàn)?.量與其對(duì)

12、應(yīng)，這樣能便與讀者理解，而不采用較優(yōu)的編碼，但保證復(fù)雜度不變。4.因作者缺乏相關(guān)數(shù)據(jù)，本程序只通過(guò)了有限的自己生成的數(shù)據(jù)，不保證程序的完全正確性。若讀者要用此出題，建議使用附件中的 Slow.dpr 對(duì)拍一下。constinf = input.txt; ouf = output.txt; maxn = 100;none = -maxlong;typeeger =long;typeXNodeType length: weight:=record eger; eger;eger;subtree:end;varn:B:eger; eger;: array1.maxn ofeger;next: arr

13、ay1.maxn shl 1 ofwho: array1.maxn shl 1 of w, l: array1.maxn shl 1 ofeger; eger;eger;par: array1.maxn ofeger;X: array1.maxn of XNodeType;hweight: array1.maxn ofeger;eger;p1, p2: array1.maxnoflq:eger;q: array1.maxn of mu, mv: array1.maxnf1, f2: array1.maxneger;ofofeger; eger;eger;pm1, ll:tK:pm2: arra

14、y1.maxn of eger;eger;Killer:Answer,array1.maxn, 1.2ofeger;AnsP1, AnsP2:eger;procedurebeginedge(a, b:eger; length, weight:eger;bk:);inc(ll);wholl := b;wll :=lll := nextllaweight; length;:=:= ll;a;if bk then edge(b, a,end;length, weight, false);procedure reEdge(a:begineger; ww:eger);nextww :=a := ww;e

15、nd;a;procedure init; vari:eger;x, y, length, weight: begineger;assign(input, inf); reset(input); read(n, B);for i := 1 to n - 1 do beginread(x, y, length, weight); edge(x, y, length, weight, true);end; close(input);end;function varCt:re:getWorkableRoot(x:eger):eger;eger;eger;function Count(root:eger

16、; par:vareger):eger;e:t: begint :=e :=eger;eger;0;root;while e 0 do beginif whoe par theninc(t, Count(whoe, root); e := nexte;end; inc(t); Count := t;end;function Work(root:vareger; par:eger):eger;e:t: beginWork e :=t :=eger;eger;:=0;root;0;while ebegin 0 doif whoe parbegintheninc(t, Work(whoe, root

17、);if re -1 then exit; end;e := nexte; end;inc(t);if t re Workend; Ct shr 1 then:= root;:= t;beginCt := Count(x, 0); re := -1;Work(x, if re =end;0);-1 then getWorkableRoot := x elsegetWorkableRoot:=re;procedurevarsetRoot(root:eger; parent:eger);e:begineger;parroot := parent;e :=root;while e 0 do begi

18、nif whoe parent then setRoot(whoe, root);e := nexte; end;end;procedure CalcX(root:procedure Work(root: vareger);eger; parent:eger);e: begine :=while begineger;root;e 0 doif whoe parent then beginXwhoe.length := Xroot.length Xwhoe.weight := Xroot.weightif Xroot.subtree 0 then+ le;+ we;Xwhoe.subtree :

19、= elseXwhoe.subtree :=Work(whoe, root); end;e := nexte; end;end; beginXroot.length := 0;Xroot.weight := 0;Xroot.subtree := 0;Work(root, 0); end;Xroot.subtreewhoe;procedure CalcHweight0(root0:eger);procedure Work(root:eger; parent:vareger);e:begineger;if (Xroot.length =hweightroot0)thenbeginhweightro

20、ot0 := Xroot.weight; p1root0 := root0;p2root0 := root;end;e :=root;while e 0 do beginif whoe parent then Work(whoe, root);e := nexte; end;end; beginhweightroot0 := none; Work(root0, 0);end;procedure getQ(root:eger);procedure Enum(root:vareger; parent:eger);e:eger;begininc(lq);qlq e := whilebegin:= r

21、oot;root; e 0 doif whoe parent thenEnum(whoe, root);e := end;end;nexte;vartmp: tmp2:procedure vari, j: begini := z; while i beginwhilewhileeger; eger;Sort(z, y:eger);eger;j := y; tmp := j doXq(z +y) shr 1.length;Xqi.lengthXqj.length tmp donc(i);dec(j);if i z if i Xmui - 1.weight then beginmui := qi;

22、if Xqi.subtree = Xmui - 1.subtree thenmvi := mvi elsemvi := muiend else beginmui := mui - 1- 1;1;if (Xqi.subtree Xmui.subtree) and(mvi-1=-1)or (Xqi.weight Xmvi - 1.weight) mvi := qielsemvi := mvi - 1; end;end;for i := 1 to lq do beginpm1i := Xmui.weight;thenf1i :=if mvi beginpm2iXmui.subtree;= -1 th

23、en:= none;f2i := -1;end else beginpm2i := Xmvi.weight;f2i := Xmvi.subtree; end;end;end;procedure vari, j:tmpMax:getBest(m:eger);eger;eger;tmpMax_p1, tmpMax_p2:eger;beginj := lq; for i := 1 beginwhile (jif j = 0to lq do 0) and (Xqj.length+Xqi.lengththen break;B)dodec(j);if f1j=Xqi.subtree thenbegintm

24、pMax := tmpMax_p1 tmpMax_p2end else begintmpMax := tmpMax_p1 tmpMax_P2end;Xqi.weight+pm2j;:= qi;:= mvj;Xqi.weight+pm1j;:= qi;:= muj;if tmpMaxhweightm then beginhweightm := tmpMax; p1m := tmpMax_p1; p2m := tmpMax_p2;end; end;end;procedure KillNode(root:procedure KillLink(root: vareger);eger;x:eger);e

25、:begineger;if who begininc(Tk);root = xthenKillerTk, 1 := root;KillerTk, 2 :=root := next exit;end;root;root;e :=root;while nexte 0 do beginif whonexte = x thenbegininc(Tk); KillerTk, KillerTk, nexte := exit;end;:= root;:= nexte;nextnexte;e := nexte; end;end;vare: begine := whilebegineger;root;e 0 doKillLink(whoe, e := nexte;end;end;root);procedure proc(x:eger);forward;procedure ProcChildren(m:vareger);e: begine := whilebegineger;m;e 0 doproc(whoe);e := nexte; end;end;procedure proc(x: varm:eger;begineger);m := getWorkableRoot(x); setRoot(m, 0);CalcX(m);CalcHweight0(m);ge