感覺自己起了個很高級的名字，開心 1.POJ 2395 Out of Hay 好像是叫最小瓶頸生成樹，要求生成樹中的最大邊最小。 其實最小生成樹的最大邊就是要求的值。 用反證法，首先假設最小生成樹為T1,最大邊為E1,另外一棵最大邊更小的生成樹為T2，最大邊為E2。 如果E2 < E1，則T2中所有的邊權值均小于E1，E1在T1中連接兩個連通分量A,B，在T2中一定有連接A,B兩個連通分量的邊（否則整個樹就不聯(lián)通了），這些邊都小于E1，用他們替換E1，則T1的總權值更小，與 T1是最小生成樹矛盾。 因此最小生成樹的最大邊的權值就是所有生成樹最大邊權值的最小值。 （聽說最小生成樹第K小的邊是所有生成樹第 K小的邊中最小的，不知道怎么證明）

2.HDU 4126 Genghis Khan the Conqueror 一個圖，改了一條邊，求最小生成樹權值和。 這題的難點是會改10000次。 首先，如果被修改的邊不在最小生成樹上，最小生成樹不變。 如果修改的邊在最小生成樹上，最小生成樹被分為A,B兩個子樹，則接下來要證明: 此時的最小生成樹是A , B兩棵子樹 + 連接 A,B兩棵子樹最小的邊。（1） 首先要明確證明的思路：直接證明好像不好做，只好用反證，反證的矛盾在哪找？只有條件——原來是最小生成樹。

次小生成樹也能再變小，進行一次換邊操作就可以變小，而這時候得到的顯然就是最小生成樹，最小生成樹之間可以通過換邊操作互相改變，而且途中經(jīng)過的都是最小生成樹。 （還沒想清楚）

3.HDU 4786 這題用到的引理其實和上面一題一樣： 任何一棵非最小生成樹的生成樹一定可以通過換一次邊的方法得到權值更小的生成樹。（1）

先把白的權值為0，黑的權值為1跑一邊MST，再把白權值為1，黑權值為0跑一邊MST，可以得到白色的最大值和最小值， 而我們要證明的是白色可以，并且只能取到min和max之間的所有值。 從max的生成樹開始，假設白色為1，黑色為0，這顆生成樹一定可以通過換邊變得更小，那么一定是把白邊換成了黑邊，而且每次都可以更小，直到他成為最小生成樹。 就是這么神奇。