若火险点数 m≤2,两座瞭望台可直接放在火险点上,答案为 0。
否则先把非火险叶子不断剥掉,得到连接所有火险点的核心树。在核心树上求加权直径端点 a,b 及路径 P。最优的两座瞭望台可以假定都在 P 上。
每个火险点投影到 P 上某点 p,记垂距 h,同一 p 取最大垂距 H(p)。二分答案 D:对每个投影点得到 P 上允许放置瞭望台的区间,用“按右端点排序、贪心放置不超过两个离散点”判定能否覆盖全部区间。二分上界取 ⌈diam/2⌉。
林区防火通道构成一棵 n 个节点的无向连通树,通道 (u,v) 的通行耗时为正权 wuv。其中有 m 个互不相同的火险点需要重点监视。指挥部决定恰好设立 2 座瞭望台(可以建在任意节点上,包括火险点本身),每个火险点由距离它更近的那座瞭望台负责;带权距离指路径上边权之和。
为了把最坏情况下的响应时间压到最低,需要使所有火险点到最近瞭望台的最大带权距离 D 最小。求该最小的 D。
约束:火险点数满足 2≤m≤n≤200000,边权不超过 100000。
第一行两个整数 n,m,表示节点数与火险点数。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.