英雄哪里出來

      線性同余(模方程組)

      
      題意：給定數(shù)組A( A[i] <= 2*10⁹ )，求非負(fù)整數(shù)數(shù)組X，使得 (A*X) MOD P == B。

      題解：根據(jù)題意，對(duì)于數(shù)組A，X，個(gè)數(shù)N以及除數(shù)P和余數(shù)B，可得

       ( A[0]*X[0] + A[1]*X[1] + A[2]*X[2] + ... + A[N-1]*X[N-1] ) MOD P = B                (1)

稍微做一下變形，可得(2)式：

       ( A[0]*X[0] + A[1]*X[1] + A[2]*X[2] + ... + A[N-1]*X[N-1] ) + K * P = B   (K為任意整數(shù)) (2)

由于K為任意整數(shù)，所以我們可以將它拆成K₀ + K₁ + K₂ ... + K_N-1，然后分別和前面N項(xiàng)去匹配，得到下面的等式：

       (A[0]*X[0] + K₀*P)  + (A[1]*X[1] + K₁*P) + ... + ... (A[N-1]*X[N-1] + K_N-1*P) = B         (3)

根據(jù)擴(kuò)展歐幾里得定理，ax + by = GCD(a, b) 必定有整數(shù)解，于是(3)式可以轉(zhuǎn)化為

       GCD(A[0], P) * T₀  +  GCD(A[1], P) * T₁ + ... + ... GCD(A[N-1], P) * T _N-1    = B        (4)

令A'[i] = GCD(A[i], P),  X'[i] = T_i，(4)可以簡(jiǎn)化為

       A'[0]*X'[0] + A'[1]*X'[1] + A'[2]*X'[2] + ... + A'[N-1]*X'[N-1] = B                     (5)

這時(shí)我們可以發(fā)現(xiàn)，(2)和(5)的形式是一樣的，只不過(2)有N+1項(xiàng)，(5)有N項(xiàng)，所以根據(jù)數(shù)學(xué)歸納法，進(jìn)過N次操作之后，最后的等式必定可以轉(zhuǎn)化成 ax = B 的形式，這里的a為所有A[i]的GCD，這個(gè)x當(dāng)且僅當(dāng)a整除B的時(shí)候有解，然后根據(jù)x的值可以遞推求出上一層的值，經(jīng)過N次迭代就可以將所有的X[i]求出來了。

       注意：迭代過程中，各種乘法有可能會(huì)整數(shù)越界，所以每次計(jì)算出的結(jié)果要對(duì)P求余，如果值小于零需要再加上P。

      枚舉

      題意：求滿足方程組

P₁*x₁ - N₁*x₁ + P₂*x₂ - N₂*x₂ = P
      P₁ + N₁ + P₂ + N₂ = K

的正整數(shù)解(P₁ , N_1­, P₂, N₂)。x₁, x₂ (0 < x₁ , x₂ < 40 000), P (-40 000 < P  < 40 000) and K(0 <= K < 2*10⁹)

題解：首先將第一個(gè)方程變一下形，可以發(fā)現(xiàn)：

（P₁ - N₁）x₁ + （P₂ - N₂）x₂ = P 其實(shí)是一個(gè)模線性方程，而P的范圍很小，所以可以考慮枚舉（P₁ - N₁）的值，枚舉范圍為[-40 000, 40 000]。如果在這個(gè)范圍內(nèi)找不到解，那么在更大的范圍必定也找不到解。

所以令a = P₁ - N₁,

1）如果 (P - a*x₁) mod x₂不等于零，則說明這個(gè)枚舉的a非法，因?yàn)?/span>P₂ - N₂必須為整數(shù);

2）否則，b = P₂ - N₂ = (P - a*x₁) / x₂;

3）a + b = (P₁ + P₂) - (N₁ + N₂)

   K     = (P₁ + P₂) + (N₁ + N₂)

所以如果 a+b 和 K的奇偶性必須保持一致，否則說明枚舉的a非法，繼續(xù)枚舉下一個(gè)；

4）令 c = P₁ + P₂ = （a+b+K）/ 2

5）將四個(gè)未知數(shù)用P1來表示：

a)         P₁ = P₁

b)        P₂ = c - P₁

c)        N₁ = P₁ - a

d)        N₂ = c - b - P₁

由于四個(gè)未知數(shù)都是非負(fù)整數(shù)，所以有

a)  P₁ <= c

b)  P₁ >= a

c)  P₁ <= c - b

d)  P₁ >= 0

       那么P1 的左區(qū)間為 Max(a, 0), 右區(qū)間為Min(c, c - b),如果左區(qū)間小于右區(qū)間，則當(dāng)前枚舉的a無解，否則說明找到一個(gè)可行解，P1直接取Max(a, 0), 就可以順勢(shì)算出N1、P2、N2的值了。

142 Keyword

      IDA*  +  HASH

      題意：給定一個(gè)長(zhǎng)度為N(N <= 5*10⁵)的字符串T（只包含'a'或'b'），求一個(gè)最短的字符串S（只包含'a'或'b'），并且S不是T的子串。

      題解：可以這么考慮，對(duì)于一個(gè)長(zhǎng)度為N的串，它有長(zhǎng)度為L的子串（1 <= L <= N），這種子串的個(gè)數(shù)為X = N - L + 1,  理論上最大允許的子串種數(shù)為 Y = 2^L。則 Z = Y - X = 2^L - (N - L + 1) = 2^L + L - N - 1, 可得Z為對(duì)于自變量L的增函數(shù)，當(dāng)L = N 的時(shí)候 Z = 2^N - 1 > 0, 所以實(shí)際最大子串種數(shù)會(huì)遠(yuǎn)遠(yuǎn)高于出現(xiàn)的子串?dāng)?shù)，于是可以通過枚舉子串的長(zhǎng)度L，然后利用深搜枚舉每一位是'a'還是'b'，當(dāng)枚舉完畢一個(gè)長(zhǎng)度為L的子串后判斷是否是原串的子串，如果不是則直接輸出解，結(jié)束搜索過程。否則繼續(xù)枚舉下一個(gè)，當(dāng)所以長(zhǎng)度為L的子串枚舉完畢都沒有找到解，則枚舉L + 1的情況。

       由于每個(gè)字符串只有'a'和'b'兩種字符，所以可以將每個(gè)字符串壓縮成一個(gè)二進(jìn)制的整數(shù)，例如： aab 可以表示為 001， bbbaa可以表示為 11100，以此類推...

       判斷是否是子串的操作也可以不需要進(jìn)行字符串逐個(gè)比較，只要在枚舉之前對(duì)源字符串的所有長(zhǎng)度為L的子串進(jìn)行一次哈希，然后枚舉完畢在哈希數(shù)組中查找是否出現(xiàn)即可，每次查找復(fù)雜度O(1)。

       長(zhǎng)度為 500000，結(jié)果少看了一個(gè)0，將數(shù)組開成了 50000，悲劇...；

143 Long Live the Queen

      動(dòng)態(tài)規(guī)劃(樹形DP)

      題意：給定一顆樹，和樹上每個(gè)結(jié)點(diǎn)的權(quán)值，求一顆子樹，使得權(quán)和最大。
      題解：用DP[1][i] 表示i這個(gè)點(diǎn)選中的情況下，以i為根的子樹的權(quán)和最大值;

         用DP[0][i]表 示i這個(gè)點(diǎn)不選中的情況下，以i為根的子樹的權(quán)和最大值;

DP[1][i] = v[i] + sum{ DP[1][v]  v是i的直接子結(jié)點(diǎn) && DP[1][v] > 0 }

DP[0][i] = max( 0, max{ max( DP[0][v], DP[1][v] ), v是i的直接子結(jié)點(diǎn) } )
            這樣，構(gòu)造一個(gè)以1為根結(jié)點(diǎn)的樹，然后就可以通過dfs求解了。這題題目要求求出的樹為非空樹，所以當(dāng)所有權(quán)值都為負(fù)數(shù)的情況下需要特殊處理，選擇所有權(quán)值中最大的那個(gè)作為答案。

144 Meeting

      概率題

      題意：A和B兩個(gè)人想要在(X,Y)這個(gè)時(shí)間段內(nèi)見面，但是如果某個(gè)人先來，他等的時(shí)間超過了Z，他就會(huì)走，他們就見不到面了。問他們能見面的概率。

      題解：面積法。畫個(gè)圖就明白了。

圖1

       x軸表示A出現(xiàn)的時(shí)間，y軸表示B出現(xiàn)的時(shí)間，平面坐標(biāo)的點(diǎn)表示他們出現(xiàn)時(shí)間的集合，只有當(dāng)點(diǎn)在橙色區(qū)域內(nèi)，才能相遇。假設(shè)A在t1時(shí)刻出現(xiàn)，B在t2時(shí)刻出現(xiàn)，那么

只有當(dāng) |t1 - t2| <= Z 時(shí)才可能相遇，將不等式化簡(jiǎn)就可以得到上圖，所以最后的概率就是圖中的六邊形區(qū)域面積 除上 正方形的面積。

       即：
            A = 60 * (Y - X)
            B = 60 * (Y-X) - Z
            P = 1 - B*B / (A*A)

145 Strange People
      啟發(fā)式搜索

      題意：給定N(N<=100)個(gè)點(diǎn)和M(M <= N*(N-1))條單向邊，以及起點(diǎn)S和終點(diǎn)T，求從S到T的第K(K <= 500)短簡(jiǎn)單路（每個(gè)點(diǎn)只能訪問一次）。

      題解：首先，利用反向邊求出終點(diǎn)T到所有點(diǎn)的最短路d[i]，那么d[S]表示從S到T的最短路。令maxLength = d[S]，然后利用dfs搜索從S到T，長(zhǎng)度不超過maxLength的簡(jiǎn)單路徑，如果找到的路徑總數(shù)大于等于K，則結(jié)束搜索，這時(shí)的maxLength表示第K條路徑的長(zhǎng)度；否則增大maxLength的值，重復(fù)上述步驟，直到maxLength為無窮大都找不到K條路徑的時(shí)候就表示沒有第K短路。

       在進(jìn)行搜索的時(shí)候，需要加上一些剪枝：

       1) 可達(dá)性剪枝

       假設(shè)當(dāng)前訪問到的點(diǎn)為u，之前已經(jīng)訪問過的點(diǎn)的集合為vset。那么利用BFS可以在O(n)的時(shí)候內(nèi)判斷u到T是否可以在不經(jīng)過vset的情況下可達(dá)。

       2) 啟發(fā)式剪枝

       假設(shè)當(dāng)前訪問到的點(diǎn)為u，本次搜索中從S到u的距離已知，為length(S, u)，而之前已經(jīng)計(jì)算出從u到T的最短估計(jì)距離為d[u](即A*中的估價(jià)函數(shù)，之所以稱之為估價(jià)，是因?yàn)樗⒉皇钦嬲淖疃叹嚯x，因?yàn)樵?/span>S到u這條路徑上可能訪問了u到T這條最短路徑上的點(diǎn)，所以真正的最短距離肯定大于等于d[u])。如果length(S, u) + d[u] > maxLength，則表明當(dāng)前這種策略中，從S經(jīng)過u到達(dá)T的最短距離已經(jīng)大于給定的長(zhǎng)度，就不用往下搜索了。

       在搜索的過程中，每次搜索到某個(gè)點(diǎn)u的時(shí)候都可以找到一個(gè)值vLength = length(S, u) + d[u]，我們?nèi)∷?/span>vLength中滿足大于maxLength 的值的最小者作為下一次搜索時(shí)的最大長(zhǎng)度maxLength，使得maxLength不是以每次加1的方式累加，從而減少了很多不必要的枚舉，可以大大加快找到第K短路的速度。

       3) 二次啟發(fā)剪枝

       啟發(fā)式剪枝可以解決大多數(shù)隨機(jī)數(shù)據(jù)，但是對(duì)于某些特殊設(shè)計(jì)的數(shù)據(jù)，還是得想更好的剪枝，例如圖2所示，起點(diǎn)為S，終點(diǎn)為T，除了起點(diǎn)和終點(diǎn)，其它點(diǎn)形成一個(gè)完全圖，邊的權(quán)值均為1。如果采用上面的方法進(jìn)行啟發(fā)，最短路d[S]為2，次短路則為10000+1+1 = 10002，但是除了終點(diǎn)以外，任何一個(gè)點(diǎn)到達(dá)T的最短路都是2，即d[i] = 2 (i != T)，這意味著length(S, u) + d[u]不能很好的起到啟發(fā)的作用，會(huì)讓maxLength還是以加1的方式逐漸累加，然后就有可能出現(xiàn)這種情況：從S出發(fā)，進(jìn)入到完全圖中走了一大圈，然后到達(dá)和T相連的那個(gè)點(diǎn)發(fā)現(xiàn)邊權(quán)值為10000，遠(yuǎn)大于maxLength，但是這個(gè)狀態(tài)圖是N!的復(fù)雜度，等到搜索結(jié)束估計(jì)花兒都謝了...

       可以用d[i][j]來保存從j點(diǎn)到達(dá)終點(diǎn)T，并且不經(jīng)過i點(diǎn)的最短路徑，同樣可以通過從T點(diǎn)反向一次預(yù)處理求得。然后每次訪問到u的時(shí)候，判斷從S到u之間的點(diǎn)中，是否有滿足length(S, u) + d[v][u] > maxLength的v，如果存在，直接剪枝，并且用最小的length(S, u) + d[v][u]作為下一次的啟發(fā)值。

圖2

146 The Runner       
      精度轉(zhuǎn)化題

      題意：一個(gè)人在一個(gè)周長(zhǎng)為L的圓上跑，每個(gè)時(shí)間段(T_i)的速度(V_i)不一樣，問最后他離起點(diǎn)的圓弧距離，周長(zhǎng)是個(gè)有四位小數(shù)的浮點(diǎn)數(shù)，其它全是整數(shù)。

      題解：首先可以考慮如果周長(zhǎng)是整數(shù)的話，就可以通過取余來求解了，而周長(zhǎng)最多只有四位小數(shù)，所以可以考慮將周長(zhǎng)和(T_i, V_i)都擴(kuò)大10000倍，全部轉(zhuǎn)化成整數(shù)后，只要將總距離Sum{ T_i * V_i } 模上周長(zhǎng)取余數(shù)即可。

       注意，這里是圓弧，圓弧是有一個(gè)優(yōu)弧和劣弧的概念的，所以要取兩條弧之間的最小值。

147 Black-white king

      區(qū)間求交

      題意：在一個(gè)N*N(N <= 10⁶)的棋盤上，有三個(gè)棋子：黑王、白王、黑白王，它們的行走方式一致，每秒向8個(gè)方向中的任意一個(gè)行走一步，如圖3所示。

圖3

       現(xiàn)在黑王和白王想要相遇(即占據(jù)相鄰的格子)，而黑白王需要阻止它們相遇，即抓住其中一個(gè)王(走到其中一個(gè)王所在的格子)，黑王和白王行走時(shí)總是走最短路徑，而黑白王走的路徑無法被縮短(即能夠走斜向的時(shí)候，不會(huì)走Z字形)，由于黑白王是隱身的，所以黑王和白王無法看見黑白王的走向，但是他們知道有它存在，當(dāng)黑王和白王走到黑白王所在的格子時(shí)不會(huì)有任何事情發(fā)生。問黑白王是否有可能抓住其中一個(gè)王，如果有可能，輸出最少步數(shù)；如果不可能，輸出黑王和白王相遇總共的行走步數(shù)。行走順序?yàn)榘淄酢⒑谕酢⒑诎淄酢?/span>

       題解：

       如果黑王和白王的y方向差值小于x方向差值，那么將三個(gè)棋子的x和y值分別交換。保證黑王和白王的y方向差值大于等于x方向差值，由于黑王和白王總是走他們能夠相遇的最短路徑，所以每次移動(dòng)一定要保證在y方向朝對(duì)方移動(dòng)一格，所以兩個(gè)王的行走區(qū)域?yàn)槌鴮?duì)方方向的一個(gè)“喇叭”形區(qū)域。

       如圖2所示，兩個(gè)王的y方向坐標(biāo)差值為T，黑王坐標(biāo)(B_x, B_y)，白王坐標(biāo)(W_x, W_y)，那么走i步后的黑王的y方向坐標(biāo)為定值B_y + i * bDir，其中bDir為黑王到白王的方向；x方向的可行區(qū)間為[B_x – i, B_x + i]和[W_x – (T-i), W_x + (T-i)]的區(qū)間交集，即圖中兩個(gè)“喇叭”形區(qū)域的交集就是黑王和白王的可行區(qū)域，最多T-1步后兩人相遇。

圖4

       黑白王的運(yùn)動(dòng)區(qū)域更加簡(jiǎn)單，如圖3所示，灰色的方形外框表示經(jīng)過3步后黑白王有可能在的位置，即一個(gè)長(zhǎng)度為2i + 1的空心正方形區(qū)域。

圖5

       于是，可以枚舉步數(shù)，判斷黑王和黑白王、白王和黑白王的第i步的區(qū)間區(qū)域是否有交集，如果一旦出現(xiàn)某個(gè)王在第i步的時(shí)候和黑白王的正方形區(qū)域有交集，則表明黑白王有可能在第i步抓住其中一個(gè)王，否則當(dāng)2i >= T-1的時(shí)候還沒有交集，表明黑王和白王已經(jīng)相遇，總步數(shù)為T-1。總復(fù)雜度O(N)。

148 B-Station

      枚舉 + 堆優(yōu)化

      題意：給定N(N <= 15000)個(gè)工作車間，每個(gè)工作車間有W_i的水量，能承受L_i的水量，如果水量超過L_i，第i個(gè)車間的所有水就會(huì)盡數(shù)流入第i+1個(gè)車間，同樣，摧毀第i個(gè)車間，那么它的水量也會(huì)流入第i+1個(gè)車間，但是摧毀第i個(gè)車間是有代價(jià)P_i的，現(xiàn)在問要讓第N個(gè)車間的水全部流出來，最小的代價(jià)是多少。
      題解：首先，暴力的辦法就是枚舉第一個(gè)被摧毀的車間k，如果存在i使得W_k + W_k+1 + ... + W_i <= Li，那么第i個(gè)車間必須也要被摧毀（否則經(jīng)過第i個(gè)車間流不過去，前面的努力就白費(fèi)了呀），這樣就可以把所有需要摧毀的車間枚舉出來，比較最小值，復(fù)雜度O(N²)，對(duì)于15000的數(shù)據(jù)量來說是行不通的。
      那么突破口在哪里呢？還是枚舉的思路，假設(shè)我們現(xiàn)在從第一個(gè)車間開始摧毀，模擬水流往下流，記錄所有需要摧毀的車間集合S；那么當(dāng)我們枚舉第二個(gè)車間開始摧毀的時(shí)候，需要摧毀的車間集合T一定是包含了 S - {1} 的；同樣，第三個(gè)車間開始摧毀的時(shí)候，摧毀的車間集合一定是包含了T - {2}的，原因很簡(jiǎn)單，起始摧毀車間編號(hào)越大，流經(jīng)某個(gè)車間時(shí)候的總水流就越小，超過下限的機(jī)會(huì)越少，越有可能要進(jìn)行人為的摧毀。為了便于理解，先來看一組數(shù)據(jù)：

    W   L   P    SumW    SumW - L

1    6   5       1         -5

2    8   3       3         -5

3    4   9       6          2

4    2   7      10          8

3   12   5      13          1

5   15   4      18          3

我們用SumW[i]記錄從第1個(gè)到第i個(gè)車間的水流總和，SumW[i] - L[i]則表示當(dāng)選定第一個(gè)車間摧毀后，水流流經(jīng)第i個(gè)車間后剩余的水量，很明顯，當(dāng)這個(gè)剩余水量小于等于0的時(shí)候，表明這個(gè)車間也要被摧毀，所以在上面這個(gè)例子中，如果選定了第一個(gè)車間摧毀，那么第二個(gè)車間也必須被摧毀。

那么，如果選定第二個(gè)車間為起始摧毀車間，其實(shí)就是在 { SumW[i] - L[i]-W[1] | i >= 2 }這個(gè)集合中找小于等于0的數(shù)的下標(biāo)，于是，算法也就應(yīng)運(yùn)而生了。

用preCost記錄枚舉第k個(gè)為起始摧毀車間的最小花費(fèi)，一個(gè)小頂堆RQ存放SumW[i] - L[i]的值，另外一個(gè)小頂堆CQ存放此次的摧毀車間集合，那么當(dāng)枚舉到第k+1個(gè)車間的時(shí)候：

　　1) 判斷RQ堆頂元素WL；

a) 如果 WL.val - SumW[k] <= 0 說明第WL.idx個(gè)車間需要被摧毀，彈出WL，將  花費(fèi)累加到preCost上，繼續(xù)1）。

b) 否則，其他車間均無須摧毀，轉(zhuǎn)到2）（因?yàn)檫@是一個(gè)小頂堆，如果某個(gè)WL.val       - SumW[k] > 0，那么以后彈出的元素至少不會(huì)比這個(gè)小）。

2) 判斷CQ堆頂元素idx；

a) 如果 idx 下標(biāo)比k+1小，那么彈出idx，將花費(fèi)從preCost中減去，繼續(xù)2）。

b) 否則，此時(shí)CQ中的元素為當(dāng)次枚舉說需要摧毀的車間，轉(zhuǎn)3）；

3) 將花費(fèi) preCost 和最小花費(fèi) MinCost 比較，更新最小花費(fèi)。

這樣一來，每個(gè)車間最多進(jìn)隊(duì)一次，出隊(duì)一次，插入、彈出復(fù)雜度均為O( log(N) )，所以整個(gè)算法復(fù)雜度為 O( N log(N) )。

149 Computer Network

      動(dòng)態(tài)規(guī)劃(樹形DP)

題意：給定一棵樹，求這棵樹上每個(gè)結(jié)點(diǎn)的最長(zhǎng)路。

題解：

       DP[0][i] 表示以i為根結(jié)點(diǎn)的子樹 中 i到葉子結(jié)點(diǎn)的最長(zhǎng)路。

       Pre[0][i] 表示導(dǎo)致此次最長(zhǎng)路的結(jié)點(diǎn)編號(hào)。

       DP[1][i] 表示以i為根結(jié)點(diǎn)的子樹 中 i到葉子結(jié)點(diǎn)的次長(zhǎng)路。

       Pre[0][i] 表示導(dǎo)致此次最次路的結(jié)點(diǎn)編號(hào)。

       從根結(jié)點(diǎn)開始遍歷，對(duì)于每個(gè)結(jié)點(diǎn)，

DP[0][i] = max{ edge(i, son) + DP[0][son]   son 為i的直接子結(jié)點(diǎn)  }

同時(shí)保存下 最長(zhǎng)路 產(chǎn)生的子結(jié)點(diǎn)的編號(hào) Pre[0][i]；

DP[1][i] = max{ edge(i, son) + DP[0][son]  son != Pre[0][i]  son 為i的直接子結(jié)點(diǎn)  }

同時(shí)保存下 次長(zhǎng)路 產(chǎn)生的子結(jié)點(diǎn)的編號(hào) Pre[1][i]；

       LN[0][i] 表示i到所有點(diǎn)中的最長(zhǎng)路。

       LN[1][i] 表示i到所有點(diǎn)中的次長(zhǎng)路。

       然后對(duì)于根結(jié)點(diǎn)1再進(jìn)行一次結(jié)點(diǎn)遍歷，更新LN[0][i]和LN[1][i]的值；

顯然，LN[0][i] >= DP[0][i]; LN[1][i] >= DP[1][i](因?yàn)?/span>DP表示子結(jié)點(diǎn)過來的最長(zhǎng)路，而LN則包含了從父親結(jié)點(diǎn)過來的最長(zhǎng)路，所以計(jì)算LN一定要先計(jì)算i的父親u的最長(zhǎng)路和次長(zhǎng)路)。

所以從1開始，1的最長(zhǎng)路和次長(zhǎng)路和次長(zhǎng)路一定是等于子結(jié)點(diǎn)過來的值（因?yàn)?/span>1為根結(jié)點(diǎn)，沒有父親）。然后遍歷1的子結(jié)點(diǎn)，每次遍歷結(jié)點(diǎn)u，更新兒子v的最長(zhǎng)路以及次長(zhǎng)路（包括導(dǎo)致此次路徑的前驅(qū)編號(hào)Pre）：

1) 選取待定最長(zhǎng)路；

       a) 如果u的最長(zhǎng)路來自v，那么待定最長(zhǎng)路為   T = LN[1][u] + edge(u, v)

       b) 如果u的最長(zhǎng)路不來自v，那么待定最長(zhǎng)路為 T = LN[0][u] + edge(u, v)

2) 將待定最長(zhǎng)路和原本v到子結(jié)點(diǎn)的最長(zhǎng)路、次長(zhǎng)路進(jìn)行比較；

       a) 如果待定最長(zhǎng)路T 比v本身的最長(zhǎng)路LN[0][v]要長(zhǎng)，那么：

              LN[1][v] = LN[0][v];   // 原本最長(zhǎng)路變?yōu)榇伍L(zhǎng)路

              LN[0][v] = T;         // 更新原來的最長(zhǎng)路為待定最長(zhǎng)路

       b) 如果待定最長(zhǎng)路T 比v本身的次長(zhǎng)路LN[1][v]要長(zhǎng)，那么：

              LN[1][v] = T;         // 更新原來的次長(zhǎng)路為待定最長(zhǎng)路

3) 比較的時(shí)候需要將前驅(qū)編號(hào)也保存下來，因?yàn)槊看芜x取待定最長(zhǎng)路的時(shí)候需要用前驅(qū)編號(hào)來判斷是選最長(zhǎng)路還是選次長(zhǎng)路。