算法总结篇---最小生成树

写在前面：

算是最后几个完成这一章节学习的了，有很多思想和技巧都很好，需要好好学习

主要涉及两个算法： (Prim) 算法和 (Kruskal) 算法

感谢lsp为本文订正做出的贡献！

例题：

黑暗城堡

先跑一遍 (Dij) 求出 (D_i)，再遍历每个点，统计有几种修建方案
然后根据乘法原理，求出所有方案数即可
~~（感觉和最小生成树没半毛钱关系是吧~~

Code

新的开始

要求将整个图的节点通电，所以发电站一定要有，并要结合电网来达到最小花费。
想象一下，电从哪来？不能凭空产出，只能从外边接（感性理解/cy）
所以可以建一个虚点(总电源)，发电站只有连接总电源才能通电。

所以这个题就转化成，另设一个虚点将所有节点连接，然后建一个总的最小生成树的板子题了

Code

构造完全图

因为给出的数据一定是最小生成树，所以直接开始建树
在建树过程中，每一次合并当成两个联通块相连

因为要求构成完全图，设两个相连的联通快分别为 (cnt_i) 和 (cnt_j) 那么两个联通块之间最多能连 (cnt_i imes cnt_j - 1) 条边（因为最小生成树的边已经统计过一次了所以要减一）
要求最小生成树唯一，所以这些边的边权是对应的 (e[i].w + 1)，统计后两个联通快记得和成一个联通块

考虑建树边统计答案这种做法的正确性：其中的任何一条边都不可能作为最小生成树的一条边，因为有比他更优的边已经连接了两个联通块（类比 (Kruskal) 的贪心原理，~~可能这道题就是为了理解这个算法的原理而存在的~~）

Code

秘密的牛奶运输 && 次小生成树

本质同严格次小生成树，只是数据范围略有不同
~~牛奶运输不是严格次小，不过用严格次小的代码竟然也能过/jk~~

大体思路：建出最小生成树 ( o) 用 (LCA) 预处理最大值的次大值 ( o) 遍历所有不在最小生成树上的边，记录统计后的答案哪个更小 ( o) 切掉此题

Code

Tree

一开始考虑先用白边生成树，再用黑边生成树。如果这样做的话，生成的树可能不是联通的。换一种说法就是有可能有不是很优的白边也可以在生成树上。

一个很奇妙的思路：

二分一个值，让白边减掉这个权值，然后跑最小生成树，当所用数量刚好等于白边并且权值最小时就是答案。注意最后的答案要加上减去的权值

正确性：通过改变白边的权值来改变白边在所有边中的位置，减得越多白边在排序中越靠前，在最小生成树中的数量也越多，反之越少。因此具有单调性，可以二分出最恰当的那个要减得权值

Code

最小生成树计数

考虑一棵最小生成树中，如果有其他建树方式，为了保证权值和不变，那么新加的边与减掉的边边权一定是相同的

那么我们统计出所有边权相同的边，并将他们分组放在一起。根据最小生成树的贪心思想，先连小边再连大边。每连一种权值的边，爆搜有多少种连边方式。最后根据乘法原理统计答案即可

我在想一个正确性：有没有一种情况，能把两条边同时替换为一大一小的两条边也能使其成为一棵最小生成树
证明：一开始就是从小到大连边，所以小的边的情况已经统计上了，这种情况在一次建树后就不可能出现（题目中说无重边和子环也是一个前提

Code