首页 > 梦想赛道
开通博客写题解
头像 SSuryxin
发表于 2021-11-02 12:42:33
梦想赛道 题目描述： 给出一颗树，你需要构造一个图使得这个树在这个图中是一个严格的次小生成树，问图的权值最小可以是多少 思路： 只需要在原树的基础上加一条边即可，因为是要最小权值，所以我们就加1，（加0的话就不是严格的次小生成树了，况且题目中给的最小权值就是1） 有个特殊的情况就是如果这个树的 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 ssllyf
发表于 2021-11-02 09:02:24
题目大意 给你一棵树，让你添加一些边，使原树是严格次小生成树，要求添加的边的边权最小 解题思路 要让原树是次小生成树，那么就要构造一棵最小生成树，又因为要边权最小，那么找一条比边权大于1的边，在两个端点之间连一条边权为1的边即可（要保证更小） 如果没有边权大于1的，那就是无解 code #inc 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”