集訓(xùn)隊(duì)2006集維護(hù)森林連通性

1、維護(hù)森林連通性動(dòng)態(tài)樹(shù)華東師大二附中陳首元?jiǎng)討B(tài)樹(shù)維護(hù)一個(gè)森林支持邊的插入與刪除支持樹(shù)的合并與分離支持尋找路徑上費(fèi)用最小的邊所有操作的均攤復(fù)雜度為O(logN)234567811020-20030-5-5Root(1,2,3,4,5,6,7,8)=1MinCost(6)=10Update(7,10)540Evert(6)新樹(shù)根Cut(4)Root(7,8)=4Link(3,4,10)動(dòng)態(tài)樹(shù)的基本操作 Root(v) 返回包含節(jié)點(diǎn)v的樹(shù)的根MinCost(v) 返回v到根路徑上費(fèi)用最小的邊Update(v,x)使v到樹(shù)根路徑上的邊的費(fèi)用+x Link(v,w,x)將以v為根的樹(shù)連接到節(jié)點(diǎn)root(w

2、)上，（v,w）的費(fèi)用為x Cut(v)刪除v與其父節(jié)點(diǎn)連接的邊Evert(v)使v成為新的根，并將v到原樹(shù)根上的邊反向操作的實(shí)現(xiàn)將樹(shù)中的邊分為實(shí)邊、虛邊兩種，每個(gè)節(jié)點(diǎn)最多向其子節(jié)點(diǎn)連出一條實(shí)邊將樹(shù)劃分為一些完全由實(shí)邊組成的路徑，只對(duì)這些路徑進(jìn)行操作一條路徑頭尾路徑的基本操作Path(v)：返回包含v的路徑 （每個(gè)路徑有一個(gè)標(biāo)志）Head(p),Tail(p)：返回首節(jié)點(diǎn)、尾節(jié)點(diǎn)Pmincost(p)：返回p中費(fèi)用最小的邊Pupdate(p,x:real)：將p中每條邊的費(fèi)用+xReverse(p)：將p中的每條邊反向Concatenate(p,q,x) ：添加邊(tail(p),head(q

3、)）費(fèi)用為x，將路徑p,q合并 Split(v)：將v從路徑中刪除并把路徑分為兩部分SpliceSplice(p) ：將路徑p向更靠近根的方向增長(zhǎng)實(shí)現(xiàn)方法：把虛邊(tail(P),Parent(p) 變?yōu)閷?shí)邊，為了維護(hù)實(shí)邊的性質(zhì)，將原來(lái)從Parent(P)中連出的邊設(shè)為虛邊ExposeExpose(v)：將從v到樹(shù)根路徑上的所有邊設(shè)為實(shí)邊 實(shí)現(xiàn)方法：不斷調(diào)用splice直到根為止有了Expose(v)，就可以實(shí)現(xiàn)所有動(dòng)態(tài)樹(shù)操作了Link操作Procedure Link(v,w:vertex;x:real);Begin Concatenate(path(v),expose(w),x);End;C

4、ut操作Function Cut(v:vertex);Var p,q:path; x,y:real;Begin Expose(v); p,q,x,y:=split(v); Dparent(v):=nil; Return y;End;路徑結(jié)構(gòu)用伸展樹(shù)保存路徑所有路徑操作都能用Splay實(shí)現(xiàn)對(duì)于Reverse與PUpdate操作，可以采用先存放修改標(biāo)志，在訪問(wèn)時(shí)修改的辦法在每次Split和Concatenate操作之后，Splay最左子孫，使它成為根復(fù)雜度分析(Expose分析)對(duì)于邊v-w（動(dòng)態(tài)樹(shù)中，不是伸展樹(shù)中）如果v的子孫w的子孫一半，稱為A類邊，否則成為B類邊。顯然每個(gè)點(diǎn)最多連出一條類邊，

5、樹(shù)中每條路徑上最多有O(logN)條B類邊。令p為B類邊中的虛邊數(shù)。復(fù)雜度分析(Expose分析)一次Expose操作，將執(zhí)行數(shù)次Splice對(duì)于每次Splice：添加一條B類虛邊進(jìn)入路徑：p+1這種情況最多發(fā)生O(logN)次添加一條A類虛邊進(jìn)入路徑：p-1可能發(fā)生許多次，但代價(jià)是p，p是保持非負(fù)的。由上面分析可以看出平均每次expose操作要執(zhí)行O(logN)次路徑操作復(fù)雜度分析(Splay分析)勢(shì)函數(shù)定義r(x)：x在動(dòng)態(tài)樹(shù)中的子節(jié)點(diǎn)數(shù)的對(duì)數(shù)伸展樹(shù)的性質(zhì)：每一次splay操作的均攤復(fù)雜度不超過(guò)：3(r(t)-r(x)+1 此性質(zhì)在勢(shì)函數(shù)定義改變后依然成立復(fù)雜度分析Expose的均攤復(fù)雜度

6、3(r(root)-r(v)+(v到樹(shù)根路徑上的節(jié)點(diǎn)數(shù)）由Expose分析得到路徑上的節(jié)點(diǎn)數(shù)平均為O(logN)復(fù)雜度為O(logN)實(shí)現(xiàn)不保存整棵樹(shù)，而保存“虛擬樹(shù)”。虛擬樹(shù)中的頂點(diǎn)與動(dòng)態(tài)樹(shù)中的是一一對(duì)應(yīng)的。虛擬樹(shù)中的每個(gè)頂點(diǎn)最多連出兩條實(shí)邊，其余為虛邊，分別成為左兒子和右兒子，其他頂點(diǎn)稱為中間頂點(diǎn)。完全由實(shí)邊組成的子樹(shù)稱為實(shí)樹(shù)。 實(shí)現(xiàn)實(shí)現(xiàn)expose需要兩種操作：一種是splay，將一棵實(shí)樹(shù)（也是二叉樹(shù)），從某個(gè)節(jié)點(diǎn)伸展使這個(gè)節(jié)點(diǎn)成為這個(gè)實(shí)樹(shù)的根。第二種是splice，將某個(gè)節(jié)點(diǎn)的一個(gè)中間節(jié)點(diǎn)變?yōu)樽髢鹤?，左兒子變?yōu)橹虚g節(jié)點(diǎn)。執(zhí)行expose(v)操作需要分為三步。首先沿v往上到虛擬樹(shù)的樹(shù)根，對(duì)沿路的各實(shí)樹(shù)進(jìn)行splay，執(zhí)行完這個(gè)步后從v到