首页 > 巨木之森
开通博客写题解
头像 W.A.R
发表于 2020-09-01 21:52:31
【牛客小白月赛27 A 巨木之森】 题意 给一棵n个结点的树，m块钱。定义从一个点出发遍历整棵树的花费是路径的边权和。 求最多能选择多少个不同的起点使得从这些起点分别遍历整棵树的花费<=m。 题解 首先，肯定的是用贪心的思想来做，假设现在已知从每个结点出发遍历整棵树的花费分别是多少，那么只需要 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 璃墨韵
发表于 2020-08-25 15:27:18
举个例子：4号点出发，走到2号点结束由图可得，每个点的代价即为每条边边权*2（红色边和蓝色边）-他走到另一个点的距离（蓝色边），由贪心显然当他走到离他最远的点时最优，此时的问题已经转换为在时间范围内求出每个点到他的最远点的距离，由树的直径的性质可知，这条直径的两个端点中必有一个是每个点的最远端，所以 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 bai_qi
发表于 2020-09-07 16:47:55
题目描述调查兵团第56次壁外调查将对巨木之森展开，已知巨木之森共有n块区域和n-1条道路，保证这n块区域联通。为了调查结果尽可能准确，兵团会派遣若干支小分队调查巨木之森，派出的小分队需满足以下规定： 1.每支小分队都可以选择从任意一块区域出发，但各支小分队的出发区域必须互不相同。 2.每支小分队都必 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”