首页 > Bunny的修路工程
开通博客写题解
头像 偶尔刷刷题
发表于 2019-08-25 11:47:06
题目大意：n个点n-1条边的一棵树，有m个点是超市；现在每个点到超市的最短距离都不超过D，至多删除多少条边，还能够保证每个点到超市的最短距离都不超过D？ 预处理：超市点的数量是x，非超市点是y，x+y = n。 1、对于不是超市的点，都需要1条边来连向超市，所以至少需要y条边，至多删除n-1 - y 展开全文
去ta的博客 赞 (4) 回复(2) 收起
头像 wzliwzli
发表于 2019-08-26 14:37:44
对于30%的数据nnn 很小，直接暴力搜索边是否选择。 对于50%的数据给 O(n2)O(n^2)O(n2) 的做法通过，自由发挥。 对于100%的数据我们可以贪心的思考，每一个城市都往最近的一个大商场前进。那么就将所有有大商场的城市都加入队列，并向外一层层拓展，如果拓展到的点是遍历过的则不加入队列 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”