原理简介
非严格次小生成树是在最小生成树有多棵时未被选为最小生成树的树，而严格最小生成树要求其边权和是第一个大于最小生成树的边权和。两者算法大致相同，都是枚举非树边加入树中，很明显会形成一棵基环树，在基环的环（不包含加入的边）中找出最大值被加入边代替更新答案，只是单纯找最大得到非严格，而找出第一个严格小于加入边权值的边得到的是严格次小生成树（被相同权值的边替换边权和不会变大哦~~~）。非严格次小生成树是在最小生成树有多棵时未被选为最小生成树的树，而严格最小生成树要求
阅读背景：
严格最小生成树
来源：互联网
分享到：
