最小生成树
Defination
给一个无向连通图,生成一颗边权和最小的树
Algorithm
Prime: 看作两个集合,每次找出集合间最小的边选入,把对应点选入。
该算法中,“集合”和“讨论集合之间的边”的思路很妙,在删边最短路和删点最短路中都有运用。
kruskal:sort边,从小到大加入。
Application
1.martix tree 定理 (咕咕)
2.对算法的思考:每一条边的地位相同,只是边权不同。本质贪心。
3.瓶颈路:做一遍最小/大生成树,倍增找路径上最大/小的边。本质贪心。
-应用:(不一定要把整棵树建出来)noip模拟T2
4.数据结构优化 动态加边/删边(只删/只加)。若形成环,该边可以替代环上任意一条边,然后 lct/树剖 维护最值即可。 删边 / 任意删边
5.动态合并(每次合并相关点数较小): 一条边试探加入,只会影响所成环上的所有边。更具体的,是环上的最值边。所以建一个有关端点的虚树,把边权压缩成两点间的最值边,每次把虚树上的边和待试探边拿来kruskal即可。sdoi2019世界地图
6.二分check。生成树在一些情况下具有单调性。如(最优比例生成树): 做一个0/1分数规划即可。
7.最优乘积生成树 即:。
- 设有 离坐标轴最近。
- 直接在每一个点的,上修改,跑最大生成树即可。
如果没有满足的,break;
否则递归{A,C},{B,C},中途取即可。