作业1湖南省长沙市长郡中学

1、An efficient algorithm for the length-constrainedheaviest path problem on a tree湖南沙郡中学源An efficient algorithm for the length-constrained heaviest path problem on atreeBang Ye Wu, Kun-Mao Chao, Chuan Yi Tang一、摘要给定一棵树，树的每条边都值和长度。要求在树中找出一个路径，路径的长度不大于给定的长度，且路径上的边权和最大。An efficient algorithm for the lengt

2、h-constrained heaviest path problem on a tree找出了一个 O(nlg2n)的方法解决此问题，并且：当边权的范围为 O(n)时复杂度可降到 O(nlgn)。同时，论：1、在给定路径长度上限时求边权和最小的路文还解决了另外三个类似径；2、在给定路径长度下限时求边权和最大的路径；3、在给定路径长度下限时求边权和最小的路径。说明：在开始这篇文章前中的简单路径(即最短路)。假设读者熟悉树的最基本概念，理解树二、问题描述设 T=(V,E)是一棵树，其中 V 是它的顶点集，E 是它的边集。w,l 分别为每条边的边权和长度函数。令 P=（PV,PE）=Path(u,

3、v)表示 u 和 v 之间唯一的简单路径，并定义： 第二步：选定一个结点 m 为根结点，令 si 表示 m 的儿子结点。第三步：对于树中的每个结点 v，计算：Xv.length=l(Path(m,v)，即根 m 至 v 的路径长度；Xv.weight=th(m,v)，即根 m 至 v 的路径的边权和；Xv.subtree=j(若v Ts )，即 v 是 m 的哪个儿子或哪个儿子的子孙。j第四步：计算一个端点在 m 的路径中的最优解，设为 hweight，即： hweight(m)=maxXv.weight|Xv.lengthB hweight(m).p1=mhweight(m).p2=v(Xv

4、.lengthB 且 Xv.weight=hweight(m)第五步：令 qi表示所有结点中到根的长度第 i 短的结点的Xqi.lengthXqi+1.length。第六步： 令 mui 表示到根的距离前 i 短的的结点中权值最大的结点， pm1i=Xmui.weight，f1i=Xmui.subtree；mvi表示表示到根的距。即使得：离前i 短的的结点中除Xmui.subtree外中的结点外权值最大的结点，pm2i=Xmvi.weight，f2i=Xmvi.subtree。若令 pm2i=-，f2i=-1。第七步：找出边权最大的结点对：for i1 to n do找出最大的 j，使 Xqj

5、.length+Xqi.lengthB若 j 不存在则进入下一步mvi不存在，则若 f1j=Xqi.subtree，则 tmpMaxXqi.weight+pm2j, tmpMax_p1qi,tmpMax_p2mvj； 否 则tmpMaxXqi.weight+pm1j,tmpMax_p1 qi, tmpMax_P2muj；若tmpMax优 于hweight(m) ， 即tmpMaxhweight(m) ， 则hweight(m)tmpMax; hweight(m).p2tmpMax_p2; endforhweight(m).p1tmpMax_p1;第八步：计算 m的最优解。最 终 结 果 ： h

6、weight=maxhweight(i) ， bestroot=i (hweight(i)=hweight) ， hweight.p1=hweight(bestroot).p1，hweight.p2=hweight(bestroot).p2。hweight为最大权，hweight.p1 和 hweight.p2 为最大权路径的两个端点。3.3 细节处理此处的选择并不是随意选择，而要选择一个点，使它的每棵的结点数不超过总结点数的一半，这样才能使复杂度为预期的复杂度。实现这个有多种方法，下面其中的一种：令 x 为一个临时根。从树的叶子结点计算以每个结点为根的的结点数，令第 i 个结点的的结点数为

7、Ti，找到出现的第一个满足|Ti|超过总结点数/2 的结点。则这个结点满足条件，设它为 m。此处的可从根开始做一个深度优先或广度优先遍历。则：1)若 v 是 m 的儿子Xv.length=l(m,v);Xv.weight= w(m,v);Xv.subtree=v2)若 v 不是 m 的儿子，设 parv 为 v 的父结点Xv.length=l(parv,v)+Xparv.length;Xv.weight=rv,v) +Xparv.weight;Xv.subtree=Xparv.subtree;此处可以直接使用快速排序，其时间复杂度为 O(nlgn)，若所有的边权为 O(n)，则可用基数排序，其

8、时间复杂度为 O(n)。此处的 mui，mvi都可以由 mui-1及 mvi-1得到，具体过程如下：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此处，当 i 递增时，j

9、 是递减的，因此，只要设置一个指针从大往小滑动即可。当 j1 时，即 j 不存在。四、拓展1、在给定路径长度上限时求边权和最小的路径：在输入后将 w(e)变为-w(e)即可。2、在给定路径长度下限时求边权和最大的路径：在输入后将 B 变为-B，l(e)变为-l(e)即可。3、在给定路径长度下限时求边权和最小的路径：在输入后将 B 变为-B，l(e)变为-l(e)，w(e)变为-w(e)即可。五、总结5.1 算法的主要 本算法的主要就是，先处理特殊情况有一个路径经过根结点，然后对于不是这种特殊情况的，将它分解到中进行处理。这是典型的递归。这使用这种时，一个重要就是如何使得复杂度不至于太高，在这个

10、算结点相对平均，这里的平均，并不是别的很法中，使用了一种技巧：使根的复杂的平均，而是简单的使结点数最多的的结点数不超过整棵树的结点个数的一半，这样的好处，就是保证了递归的层数不会超过 lg n 层。显然一个结点在每一层都至多被处理一次，所以保证了复杂度较低。5.2 算法使用的一些技巧：1)选定结点：选根结点是此算法中一个很值得借见的。其实不选根结点算法也可以正确结束，但算法复杂度将变为 O(n2lgn)，正是根结点的巧妙选取，使得算法更好的解决。2)多处采用了已知的结果：如第三步，第六步，第七步等。六、源程序program An_efficient_algorithm_for_the_leng

11、th_constrained_heaviest_pa th_problem_on_a_tree;/ An em/标题：efficient algorithm for the length-constrained heaviest path probl on a tree时间复杂度：O(n lg2 n)空间复杂度：O(n)作者：学校：湖南沙郡中学指导老师：向期中 日期：2005-04-24说明：1.本程序只解决了边长与边权为整数的情况，若其为实数，只要将相应的类型更改即可。2.本程序所解决一树的结点个数最多为 100，当要求结点个数应的值即可。时，只要将 maxn 改为相因为本程序为3.量与其对

12、应，这样能便与读者理解，而不采用较优的编码，但保证复杂度不变。4.因作者缺乏相关数据，本程序只通过了有限的自己生成的数据，不保证程序的完全正确性。若读者要用此出题，建议使用附件中的 Slow.dpr 对拍一下。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