题解——Acwing.340 通信线路
2021-01-17 06:12
阅读：457
二分答案。
对于二分的值mid，定义在所有1~n的路径中，满足权值大于mid的边的数量小于等于k者为合法路径。
当mid越大时，权值大于mid的边的数量必然非严格单调递减，故而合法路径的数量必然也非严格单调递减。
故而该问题满足如上单调性，二分答案的可行性成立。
因此，可将问题转化为判定：
对于给定的mid，是否存在一条路径，使该路径上的权值大于mid的边的数量小于等于k。
这个问题就非常好做了。只需把权值大于mid的边的权值视为1，其余边权值视为0，然后求解01最短路即可，复杂度是线性的。
最终整个算法的时间复杂度为O((N+M)logMAX_L)
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：题解——Acwing.340 通信线路
文章链接：http://soscw.com/index.php/essay/43063.html
文章标题：题解——Acwing.340 通信线路
文章链接：http://soscw.com/index.php/essay/43063.html
评论
亲，登录后才可以留言！