首页 > 代码库 > [codevs 1183][泥泞的道路(二分+spfa)
[codevs 1183][泥泞的道路(二分+spfa)
题目:http://dev.codevs.cn/problem/1183/
分析:这个和最优比率生成树很像,都可以二分答案的,只不过判定方面一个是求是否有最短路径,一个是求是否有生成树。假设等待判定的是ans,那么我们可以把每条边的边权改成s[i][j]-ans*t[i][j],然后跑最长路。如果d[n]>=0,那么肯定就说明这个ans是可行的。但是要注意有可能最长路的时候可能出现正权环,那么可以脑补以下,无论是否环中是否包含n,但都可以多走这环几次使得目前的d很大很大,以至于走了一些负边到n时候总的d[n]还是>=0,所以当出现正权环时候,我们已经可以认为这个ans可行。
[codevs 1183][泥泞的道路(二分+spfa)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。