南雅集訓(xùn)考試數(shù)據(jù)答案network解題報(bào)告

1、網(wǎng)絡(luò)升級(jí)解題1、題目大意給定一棵樹(shù) T=(V,E)以及正整數(shù) p，定義在 V 中每一個(gè)點(diǎn) v 上的函數(shù) C(v)，定義在 E 中每一條邊 e 上的函數(shù) D(e)，求一個(gè)點(diǎn)的集合 S，使得|S|p，并且使得 W(S)= C(v) mindist(u, v) | u S 最大，其中 dist(u,v)表示從 u 到 v 的唯vS vV一的路徑上所有邊的 D 值之和。2、算法分析給定一棵樹(shù)，就有理由相信有有效算法。從的貪心開(kāi)始想，然后再到調(diào)整，可以想到很多感覺(jué)比較優(yōu)的的算法。但感覺(jué)是不行的，必須要證明，而且“比較優(yōu)”也沒(méi)有實(shí)質(zhì)的意義，這里要求的是最優(yōu)。所以，這些算法有些愛(ài)莫能助的感覺(jué)。如果做樹(shù)的題目

2、做的比較多的話，就很容易形成一種由于性思維產(chǎn)生的算法，這個(gè)算法正是動(dòng)態(tài)規(guī)劃。這道題，能否利用動(dòng)態(tài)規(guī)劃來(lái)解決呢？為了方便，用“節(jié)點(diǎn)”來(lái)代替“網(wǎng)絡(luò)機(jī)”，用“中心節(jié)點(diǎn)”代替“中心網(wǎng)絡(luò)機(jī)”。再設(shè)一個(gè)函數(shù) near(v)表示距離 v 最近的中心點(diǎn)，用 control(v)表示中心點(diǎn) v控制的范圍，即 control(v)=u|near(u)=v。再直觀的感覺(jué)一下，一個(gè)中心點(diǎn)的控制范圍是一個(gè)包含自己的連通分塊（當(dāng)然，忽略了一個(gè)點(diǎn)有多個(gè)中心點(diǎn)距離他最近的情況）。樹(shù)的動(dòng)態(tài)規(guī)劃，一般是可以把每一個(gè)作為一個(gè)階段。這道題不妨也這樣考慮，設(shè)所選擇的的根節(jié)點(diǎn)的標(biāo)號(hào)為 i，那么，除了 i，轉(zhuǎn)移的狀態(tài)還需要有哪些參數(shù)呢？不

3、難發(fā)現(xiàn)，還要一個(gè)參數(shù) q 表示這個(gè)中有多少個(gè)點(diǎn)是中心節(jié)點(diǎn)。就是這樣描述一個(gè)狀態(tài)夠不夠呢？只看這棵，也以表示一個(gè)狀態(tài)，但是，這棵是整棵樹(shù)的一部份沒(méi)，這個(gè)就不得不考慮了。也許某些點(diǎn)，距離他最近的中心節(jié)點(diǎn)不是在這可中，可能是外的某一點(diǎn)。那么，只在這棵中考慮就不夠了。還需要考慮什么？注意到一個(gè)事實(shí)，在以 i 為根的中的某一個(gè)節(jié)點(diǎn) v，要么 near(v)在這可中，要么 near(v)是在外距離 i 最近的一個(gè)中心點(diǎn) u，即 near(v)=near(i)=u。如下面的圖所示：那么，一個(gè)狀態(tài)就可以用 f(i,q,u)來(lái)表示了，它表示以在 i 為根的中選擇q 個(gè)點(diǎn)，并且在這個(gè)外距離 i 最近的中心點(diǎn)是 u

4、 時(shí)，這iu個(gè)的花費(fèi)最少是多少。這個(gè)花費(fèi)包含 q 個(gè)中心點(diǎn)的 C 值control(u)和與中所有點(diǎn)到最近中心點(diǎn)（可以是 u 或者中的 q以i為根的個(gè)點(diǎn)）的距離之和的和。其中，1in，0qp，1un，用這個(gè)狀態(tài)能不能轉(zhuǎn)移？分兩種情況：一種是點(diǎn) u 的控制范圍包含 i(就是上面的圖)，那么 i 的所有兒子之間是不會(huì)互相影響的。只需要確定了每棵中中心節(jié)點(diǎn)的個(gè)數(shù)。那么就可以轉(zhuǎn)移了，而確定每個(gè)中心點(diǎn)的個(gè)數(shù)只需要再用一次動(dòng)態(tài)規(guī)劃就可以了。另一種情況是點(diǎn) u 的控制范圍不包含 i，那么，這時(shí)就只需要單獨(dú)的考慮以i 為根的了！類(lèi)似的，設(shè) g(i,q,u)表示在以 i 為根的中選擇 q 個(gè)中心點(diǎn)，這 q 個(gè)中

5、心點(diǎn)據(jù) i 最近的中心點(diǎn)是 u 時(shí)的最少花費(fèi)是多少?；ㄙM(fèi)的定義與上面的一樣，其中，1in，1qp，1un。那么加了一個(gè) g 后，這種情況下，f(i,q,u)=ming(i,q,v)|v 屬于以 i 為根的。由于這個(gè)方程的右邊沒(méi)有 u，為了降低復(fù)雜度，設(shè) h(i,q)=ming(i,q,v)| v 屬于以 i 為根的既然添加了一個(gè) g，那么就需要考慮 g 的狀態(tài)轉(zhuǎn)移。所以，f(i,q,u)=h(i,q)。g 的狀態(tài)轉(zhuǎn)移比較簡(jiǎn)單一些，只需要確定了 i 的每一個(gè)兒數(shù)，就可以遞推了，這個(gè)用動(dòng)態(tài)規(guī)劃也可以實(shí)現(xiàn)。中中心點(diǎn)的個(gè)在上面轉(zhuǎn)移 f 和 g 的過(guò)程中，都還需要用一次動(dòng)態(tài)規(guī)劃，這個(gè)使得實(shí)現(xiàn)相當(dāng)復(fù)雜，其

6、實(shí)，可以把一棵樹(shù)化成等價(jià)的二叉樹(shù)，這樣，就只需要枚舉一棵兒中中心點(diǎn)的個(gè)數(shù)，就可以知道另一棵兒中中心點(diǎn)的個(gè)數(shù)了?；鏄?shù)的辦法是：對(duì)于每一個(gè)兒子的個(gè)數(shù)為 k(k2)的節(jié)點(diǎn)，把這個(gè)點(diǎn)拆成 k-1 個(gè)點(diǎn)，一條鏈的形式，鏈頭點(diǎn)的 C 值就是原來(lái)點(diǎn)的 C 值，而其它點(diǎn)的 C 值都是+。鏈尾添加兩個(gè)兒子，其它的點(diǎn)添加一個(gè)兒子，這樣，就剛好添加了 k 個(gè)兒子,如下圖所示：這樣，就只需要考慮二叉樹(shù)的情況了。如果一個(gè)點(diǎn)沒(méi)有兩個(gè)兒子，那么相應(yīng)的兒子就看成是 0。這樣得出了下面的遞推方程式：f (i, q, j) min min f (i1, q1, j) 1, j) dist(i, j)f (i2h(i, q)1

7、, j) dist(i, j) j是i1的后代g(i, q, j) ming(i1, q1, j) f (i2min f (i , q , j) g(i , j) dist(i, j) j是i 的后代11212h(i, q) ming(i, q, j) | j是i或i的后代邊界條件是當(dāng) i=0 的時(shí)候。還有其它一些不可能達(dá)到的狀態(tài)，在上面都省掉了。來(lái)分析上面規(guī)劃的時(shí)間復(fù)雜度。求 h 只需要 O(n3)就可以了。求 f 和 g 的復(fù)雜度是一樣的，咋一看，都是 O(n4)，其實(shí)，仔細(xì)分析中間 q1 的范圍，可以得出上面規(guī)劃的時(shí)間復(fù)雜度是 O(n3)的。在實(shí)際處理中，由于 f 和 g 的參數(shù)一樣，并且不會(huì)有一個(gè)有意義的 f 與有意義的 g 的 3 個(gè)參數(shù)都是一樣的（因?yàn)橹挥?j 不是 i 或者 i 的后代時(shí) f(i,q,j)才有意義，只有 j 是 i 或者 i 的后代時(shí) g(i,q,j)才有意義），所以可以只用一個(gè)數(shù)組而達(dá)到節(jié)省空間的目的。但是，空間還需要 800*400*400*4byte512Mb 不能承受，怎么辦？可以采取只存一部分的方法。對(duì)于一個(gè) i，如果 f(i)和 g(i)都計(jì)算