首页 > 编程语言 > 详细

《算法竞赛进阶指南》 #0x61 图论 - 最短路

时间:2020-04-09 16:37:37      阅读:120      评论:0      收藏:0      [点我收藏+]

题目链接:https://www.acwing.com/activity/content/punch_the_clock/6/

Dijkstra算法

用于求解单源最短路问题。

常见的技巧有:

反向建图:源点为整个点击,汇点却只有单个,这时可能把边反向。

分层建图:指定某些边可以使用一些特殊性质,比如可以使用一些魔法降低边的权值,但是魔法力量有限。这种问题一般魔法力量的范围不会太大,刚刚好可以把原图的每个点都拆成魔法力量的范围这么多,注意提取边的公共性质来减少边的存储。

多个点同时作为源点:区别于多源最短路,这里求源点集到每个点的最短路,可以建一个超级源点,然后向源点集连权值为0的边,或者直接把整个点集都全部丢到 PQ 里面。

单源单汇:类似双向BFS,退出的时候会快一点。

340. 通信线路

题意:在郊区有 N 座通信基站,P 条 双向电缆,第 i 条电缆连接基站 Ai 和 Bi。特别地,1 号基站是通信公司的总站,N 号基站位于一座农场中。现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费 Li 。电话公司正在举行优惠活动。农场主可以指定一条从 1 号基站到 N 号基站的路径,并指定路径上不超过 K 条电缆,由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中,升级价格最贵的那条电缆的花费即可。求至少用多少钱可以完成升级。

数据范围:

0≤K<N≤1000,
1≤P≤10000,
1≤Li≤1000000

题解:

从特殊到一般,先考虑 K=0 的情形,这个时候是要找一条最短路,只不过不是加法运算而是 max 运算,用 Dijkstra 算法可以直接求解。注意到好像以前做过这类题目(貌似第一次见是2018年多校)都从分层图去考虑。观察一下数据范围,确实可以建分层图。

把一个点拆成 K+1 个点,二元组 (id,k) 表示编号为 id 的点已经使用了 k 次免费的状态,那么原本的边也拆成超级多条边,不过非常容易注意到这些边可以高度压缩。

《算法竞赛进阶指南》 #0x61 图论 - 最短路

原文:https://www.cnblogs.com/KisekiPurin2019/p/12667294.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!