P10206 [JOI 2024 Final] 建设工程 2 题解

Perta · 2024-03-19 22:00:05 · 题解

在不新建铁路线的图上跑最短路，定义此时 x,y 间的最短路长为 dis(x,y)。

特判掉 dis(S,T)\leq K 的情况（所有方案均合法），此时我们要求的就是满足 dis(S,u)+L+dis(T,v)\leq K 的无序二元组 (u,v) 数量。

令 a_i=dis(T,i)，将 a 数组从小到大排序。枚举 u，则满足条件的 v 数量有 p 个，其中 p 为最大的满足 dis(S,u)\leq K-L-a_p 的数（不存在则为 0），直接 \rm upper\_bound 即可。

答案为 \sum p，时间复杂度 O(m\log m+n\log n)。

Code

关于上述解法你或许会有个小小的疑惑：若一个二元组 (u,v) 同时满足 dis(S,u)+L+dis(T,v)\leq K 和 dis(S,v)+L+dis(T,u)\leq K，这样算不会算重吗？

答案是这种情况不存在。证明比较简单，这里不再展开。