Luogu P4180 【模闆】嚴格次小生成樹[BJWC2010] 題解

題目大意

% 　　給定一幅無向圖，求其嚴格次小生成樹。

　　資料範圍　點數非負且不超過十的五次方，邊數非負且不超過三乘十的五次方，邊權非負且不超過十的九次方。

題解

% 　　首先是一條定理：

定理1　對于任意形态的最小生成樹，至少存在一種形态的次小生成樹1與最小生成樹相差不超過一條邊。即對于任意形态的最小生成樹，僅需要替換不超過一條邊即可變成次小生成樹。

證1　如果次小生成樹與最小生成樹相差兩條邊，設邊 a a a 替換了最小生成樹中的邊 u u u，邊 b b b 替換了最小生成樹中的邊 v v v，則替換後生成樹的邊權和與替換前生成樹的邊權和的差距為 ( a − u + b − v ) (a-u+b-v) (a−u+b−v)，有四種情況：

1. l e n a &lt; l e n u , l e n b &lt; l e n v len_a&lt;len_u,len_b&lt;len_v lena​<lenu​,lenb​<lenv​：此時 a − u + b − v &lt; a + b a-u+b-v&lt;a+b a−u+b−v<a+b，與最小生成樹的定義沖突。
2. l e n a &gt; l e n u , l e n b &gt; l e n v len_a&gt; len_u,len_b&gt; len_v lena​>lenu​,lenb​>lenv​：此時如果隻用 b b b 換 v v v，次小生成樹會更小，不符合次小生成樹的定義。
3. l e n a &gt; l e n u , l e n b = l e n u len_a&gt;len_u,len_b=len_u lena​>lenu​,lenb​=lenu​：此時如果隻用 a a a 換 u u u，則會得到與最小生成樹相等的次小生成樹，相比較兩條邊都替換，顯然指後者得到的生成樹會更小與次小生成樹定義沖突。
4. l e n a = l e n u , l e n u = l e n v len_a=len_u,len_u=len_v lena​=lenu​,lenu​=lenv​：顯然隻需要換其中一條邊，即可達成與最小生成樹相等的次小生成樹。

% 　　證畢。

% 　　下面開始考慮嚴格次小生成樹，可以發現，能構成非嚴格次小生成樹（也就是和最小生成樹邊權和相等的樹）的情況隻有上述證明中的第 3 種和第 4 種情況。可以發現，在這些情況下都存在某條邊的權值等于代替換邊的權值。因而我們可以得到：

定理2　對于任意形态的最小生成樹，至少存在一種形态的嚴格次小生成樹與最小生成樹相差不超過一條替換前後權值不相等的邊。即對于任意形态的最小生成樹，至多隻需要删除一條邊，并加上一條權值不等于删去的邊的權值的邊即可變成嚴格次小生成樹。

證2　假設最小生成樹變成嚴格次小生成樹需要替換兩條替換前後權值不相等邊，設邊 a a a 替換了最小生成樹中的邊 u u u，邊 b b b 替換了最小生成樹中的邊 v v v，則替換後生成樹的邊權和與替換前生成樹的邊權和的差距為 ( a − u + b − v ) (a-u+b-v) (a−u+b−v)，有兩種情況：

1. l e n a &lt; l e n u , l e n b &lt; l e n v len_a&lt;len_u,len_b&lt;len_v lena​<lenu​,lenb​<lenv​：此時 a − u + b − v &lt; a + b a-u+b-v&lt;a+b a−u+b−v<a+b，與嚴格最小生成樹的定義沖突。
2. l e n a &gt; l e n u , l e n b &gt; l e n v len_a&gt; len_u,len_b&gt; len_v lena​>lenu​,lenb​>lenv​：此時如果隻用 b b b 換 v v v，嚴格次小生成樹會更小，不符合嚴格次小生成樹的定義。2

% 　　綜上，我們得到了一個全新的算法。

1. 先求出最小生成樹。（Prime/KrusKal）
2. 枚舉不在最小生成樹中的邊，嘗試加入最小生成樹中。
3. 加入生成樹後，必然形成一個環，在環上找一條長度嚴格小于加入的邊長度的最長的邊，嘗試斷開它，記錄答案，恢複最小生成樹。
4. 在所有答案中，取最大的答案。

% 　　其中，求環長度嚴格次小的邊可以用LCT或者倍增實作。因而總時間複雜度為 Θ ( ( n + m ) log ⁡ 2 n ) \Theta((n+m)\log_2n) Θ((n+m)log2​n)

1. 本文中次小生成樹代指非嚴格次小生成樹。 ↩︎
2. 此處給出的證明意義不大，隻是複制粘貼，僅為報複社會，可你應該還是看完了。hhh ↩︎