最小生成树若干性质以及在ACM中的应用

感觉自己起了个很高级的名字，开心 1.POJ 2395 Out of Hay 好像是叫最小瓶颈生成树，要求生成树中的最大边最小。 其实最小生成树的最大边就是要求的值。 用反证法，首先假设最小生成树为T1,最大边为E1,另外一棵最大边更小的生成树为T2，最大边为E2。 如果E2 < E1，则T2中所有的边权值均小于E1，E1在T1中连接两个连通分量A,B，在T2中一定有连接A,B两个连通分量的边（否则整个树就不联通了），这些边都小于E1，用他们替换E1，则T1的总权值更小，与 T1是最小生成树矛盾。 因此最小生成树的最大边的权值就是所有生成树最大边权值的最小值。 （听说最小生成树第K小的边是所有生成树第 K小的边中最小的，不知道怎么证明）

2.HDU 4126 Genghis Khan the Conqueror 一个图，改了一条边，求最小生成树权值和。 这题的难点是会改10000次。 首先，如果被修改的边不在最小生成树上，最小生成树不变。 如果修改的边在最小生成树上，最小生成树被分为A,B两个子树，则接下来要证明: 此时的最小生成树是A , B两棵子树 + 连接 A,B两棵子树最小的边。（1） 首先要明确证明的思路：直接证明好像不好做，只好用反证，反证的矛盾在哪找？只有条件——原来是最小生成树。

次小生成树也能再变小，进行一次换边操作就可以变小，而这时候得到的显然就是最小生成树，最小生成树之间可以通过换边操作互相改变，而且途中经过的都是最小生成树。 （还没想清楚）

3.HDU 4786 这题用到的引理其实和上面一题一样： 任何一棵非最小生成树的生成树一定可以通过换一次边的方法得到权值更小的生成树。（1）

先把白的权值为0，黑的权值为1跑一边MST，再把白权值为1，黑权值为0跑一边MST，可以得到白色的最大值和最小值， 而我们要证明的是白色可以，并且只能取到min和max之间的所有值。 从max的生成树开始，假设白色为1，黑色为0，这颗生成树一定可以通过换边变得更小，那么一定是把白边换成了黑边，而且每次都可以更小，直到他成为最小生成树。 就是这么神奇。