Luogu P1084 疫情控制 题解

Link

Luogu Problem view

Describe

有一棵以$1$为根节点的树,现在要在除根节点外的点设立阻拦,使得没有一条路径可以从根节点到任意一个叶子节点。这些阻拦需要$m$个军队来设立,这$m$个军队中第$i$个一开始在点$q_i$上,军队移动的时间等于移动经过的边权之和,问最少要多少时间才能设立完阻拦。注意:不同的军队可以同时移动。
对于$100%$的数据,$2\leq m\leq n\leq 50,000,0\leq w\leq {10}^9$($w$表示边权)。

Solution

由题意可知,要求的是最少的时间,所以显而易见可以二分(如果花了更长的时间肯定更可以),接下来就只需要考虑如何写$check$函数。
我们有一个贪心的想法:因为要阻拦从根到叶子节点的路径,所以军队越往上肯定就越好,这样可以阻拦更多的路径。
如果一个军队可以走到根节点,则将这个军队先放一放,因为这个军队可能会走到另一个以根节点的子节点为根的树中去。
如果一个军队不可以走到根节点,则走到能走到的深度最小的点上。
经过这次操作后,再遍历一次,记录还是可以到达的叶子节点。再贪心的思想:剩余时间最少的军队到叶子节点肯定是最优的,然后再操作一遍,把剩余节点按照到根节点的距离进行排序。
现在可能还有一些军队还未设立阻拦,将这些军队按照剩余的时间进行排序,然后与刚刚排序过的剩余的节点一一匹配,这也是个贪心策略,如果所有都能够被匹配则可行,否则不可行。

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇