标签: 生成树

1 篇文章

CF1184E1 Daleks’ Invasion (easy) 题解
题意 题目链接 easy version 中要求的是将第一条边最大修改为多少能够使其存在在最小生成树中。 解析 题目与最小生成树相关,又要值尽可能大,很容易想到 kruskal 算法,因为该算法是先将权值小的边加入到最小生成树中的,因此,我们希望第一条边能够尽可能晚的加入到最小生成树中,这样才能使其权值最大。 考虑到要使其尽可能晚加入而且不能不加入…