東北育才學校【n個節點的樹以及每個節點k棵子樹，使得子樹中所有節點權值和的最小值最樹的劃分問題是圖論中的一類范圍非常廣泛的問題，這類題目的大意就是將給定的一一、問題的提草莓（NOI2003Day2-2berry 給出一片草莓中每個草莓的重量以及它們的連接情況。定義：sum(i)i塊草莓田中所有草莓重量的和（1<=ik）,xmin{sum(i)|1<=i<=k。你的任務就是要把一塊草莓田分割成k塊，且分割方案需要滿足如下的條件：·x盡可能的大。69個數據所給的圖是一棵樹，若不k棵子樹，定義：sum(i)i棵子樹中所有節點權值的和，x=min{sum(i)|1<=i<=k}，請求出x的最大值并輸出此時的劃分方案。二、算法1：轉化問個節點，計算以此節點為根的完全的權值和，若權值和使得劃分的最大數目不小于k，x既為原問題的解。我們終于找到了一種解決問題的途徑，但問題是否已經被完美的解決了呢？當我們分如果每個節點權值的上界是c(no(c)ey三、算法2：移動算，后達到某個目標狀態。初始狀態的選擇并不，我們可以任取一個度為1的頂點為根，然使得其最后終止時會達到我們期望的最小最大的要求。樹的權值和我們取出其中新權值和最大的那一種與當前未移動時的的最小權值和進1k-1個割都計算出當前劃分狀態下 Wnow最大的那種移動。算法結束，Wmin既為所求的最大的最小值，當前劃分法在第一時間內用來確定它是對的，我們還需要對它進行的研究和分析。 A在劃分A’的上方，也就是存在一種AA’的割的一一對應，使得每個A的割都在它A’的割的上方。這種定義能夠形象的表現出上方的含義，不失為一種不錯的定義在這之前，讓我們先定義一下部分的概念：若一棵T的T’包含了頂點v連同v的某一個兒子以及這個兒子的所有后繼則稱T’是T在頂點v處的一棵部分與v相T’的初始邊。接下來我們在樹T上的兩個劃分A和A’，若A在A’上方，則對于任意一棵T的部分，我們發現，若A中有一個割c在上，因為這個割所對應的A’中的割c’是在c的下方，所以c’也一定在這棵部分上。如果將劃分A在一棵部分上的割的數目表示為#(A)。我們得到了如下性質：若劃分A在A’上方，則對于樹T的任意一棵部分，都有#(A)#(A’)。這條性質在下面的證明過程中起到了非常重要的作用。，下面我們便來到了最的部分為了證明算法的正確性試圖證明如下幾點，在初始狀態時的劃分AQ若存在一個最優劃分QA是在QAQ設A在Q的上方且A不等于Q，在算法進行一步后A變為A’， 一個最優劃分Q’使得A’在Q’上方。 QAQAQ不相等（A不是最優劃分，由(2)得算法一定還會繼續，與算法終止，故算法終止時的劃分一定為最優劃分。使得最小最大的劃分。用Wmin(A)表示在劃分A下的最小的權值，則對于任意一A，都有Wmin(A)Wmin(Q)。(2)若存在一個最優劃分Q使得當前的劃分A是在Q的上方A和Q不相等，證：因為AQ不相等，故在A中必存在一個割使得在同一條邊上沒有Qc為滿足此條件的深度最大的割，由于在以c所在的邊為初始邊的部分上，#(A)≤#(Q)，且c所在的邊上沒有Q的割，所以在中必存在一個Q的割s使得在同一條邊上沒有A的sAc’c’sc’所對應的新的權值和≥s所對應的權值和≥Wmin(Q)≥Wmin(A)（因為Q是最優劃分，所以算法一定會繼續，且移動后的割所對應的新的權值和一定不小于Wmin(Q)。證畢上面的證明還順便得出了另一個結論每次經過算法移動后的割所對應的新的權值和一定不小于Wmin(Q)，這個結論 (3)設A在Q的上方且A不等于Q，在算法進行一步后A變為A’， 能找到一個最優劃分Q’使得A’在Q’上方。c從邊e1移動到了e2，設邊e1e2v。為了構造Q’,情況1：對于在頂點v處的每一棵部分T’，都有#(A)=#(Q)則經過移動后對于以e2為初始邊的部分有#(A’)=#(Q)+1，由于在以e1為初始邊的部分中#(A)≤#(Q)，故在邊e1上必有Q的一個割，不妨設為s，將s從e1移動到方的。所以在T’中，s所對應的一定是包含c所對應的的。所以s所對應的權值和≥c對應的權值和≥Wmin(Q)((2)的證明中的得出的結論)，所以Q’也是一個最優A’Q’上方的。情況2：存在在頂點v處的某棵T’使得#(A)<#(Q)如果在以e2為初始邊的中就有#(A)<#(Q)，則A’≥Q，既Q就是符合條件的劃分。若在以e2為初始邊的中#(A)=#(Q)，則由假設我們可以設存在一條從v出發的邊e3使得在以e3為初始邊的部分T’中#(A)<#(Q)，設s為Q在T’中深度最小的割，將s移至e2處，構成劃分Q’。則A’是在Q’的上方的。與情況1一樣，s所對應的新的權故Q’也是一個最優劃分，且A’在Q’上方。 情況 情況Ok2rd(T)+kn)rd(T)是這棵樹的半徑，具體的算法實現比較復雜，這里就不詳細講了，有的朋友可以參考一下相關的。值的直徑等等這個算法是不是依然適用呢？我們發現在算法正確性的證明過程中，用了權函數的一個性質：若T’是T的任意一棵，則必然有W(T)≥W(T’)，其中W(T)k棵子樹，使得的最大值最小，或是最大值與最小值的差最小等等問題，我們是不是也可以用122k－1根相連的唯一一條邊上得到的，這樣做的好處是一定可以保證它是在某個最優劃分的上方，（樹中所有節點的權值和）/(k-1)，則算法劃分出來的數目一定不超過k-1剩余12便巧妙的結合在一起了。，四、總1主要應用了問題轉化的思想，將原問題轉化為新的，容易解而算法2則從另一個角度看問題，將目光集中再分割的“割”上面，從而得到了一個復RonaldI.BeckerandYehoshuaPerl,Theshiftingalgorithmtechniqueforthepartitioningoft