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

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

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

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

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

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

6、實，可以把一棵樹化成等價的二叉樹，這樣，就只需要枚舉一棵兒中中心點的個數(shù)，就可以知道另一棵兒中中心點的個數(shù)了?；鏄涞霓k法是：對于每一個兒子的個數(shù)為 k(k2)的節(jié)點，把這個點拆成 k-1 個點，一條鏈的形式，鏈頭點的 C 值就是原來點的 C 值，而其它點的 C 值都是+。鏈尾添加兩個兒子，其它的點添加一個兒子，這樣，就剛好添加了 k 個兒子,如下圖所示：這樣，就只需要考慮二叉樹的情況了。如果一個點沒有兩個兒子，那么相應(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 的時候。還有其它一些不可能達到的狀態(tài)，在上面都省掉了。來分析上面規(guī)劃的時間復(fù)雜度。求 h 只需要 O(n3)就可以了。求 f 和 g 的復(fù)雜度是一樣的，咋一看，都是 O(n4)，其實，仔細分析中間 q1 的范圍，可以得出上面規(guī)劃的時間復(fù)雜度是 O(n3)的。在實際處理中，由于 f 和 g 的參數(shù)一樣，并且不會有一個有意義的 f 與有意義的 g 的 3 個參數(shù)都是一樣的（因為只有 j 不是 i 或者 i 的后代時 f(i,q,j)才有意義，只有 j 是 i 或者 i 的后代時 g(i,q,j)才有意義），所以可以只用一個數(shù)組而達到節(jié)省空間的目的。但是，空間還需要 800*400*400*4byte512Mb 不能承受，怎么辦？可以采取只存一部分的方法。對于一個 i，如果 f(i)和 g(i)都計算