题目描述
求严格次小生成树 写题解纪念
算法
-
求出最小生成树
-
选择未被选择的一条边
-
把这条边连接上 替换最小生成树中相应的连接两个点的路径上的边的最大值 因为是严格次小生成树,相等的就不替换了
-
取最小值便为最小生成树
为什么会对?
最小生成树中相应的连接两个点的路径上的边的最大值 一定比我们选择的边小
不然最小生成树就不是这棵了。
细节
我们可以通过dfs记录每两个点最小生成树的路径上的最大值
还要记录次大值(严格和最大值不一样的次大值)
为什么?
题目中求的是严格最小生成树
所以我们等于最大值的就不替换,但我们可以替换成次大值啊
为什么次大值可以满足?
因为我们选择的这条边不可能大于最大值 只可能等于最大值
如果等于
次大值肯定小于他。
记得dfs
时max1
,max2
不能改变。
记得long long
完。