首页 > 其他 > 详细

【20181023T3】“新”的家园【虚图】

时间:2018-10-25 10:36:50      阅读:167      评论:0      收藏:0      [点我收藏+]

打死也不告诉你这个名字是我编的

题面

【错解】

哎最短路欸

哎floyd+dijkstra有30分

骗分骗分

【正解】

我们发现n和m(不是E)不是一个数量级的

也就是说,在做传统最短路的时候,很多时间都浪费在环上

我们再看一下,如果我们把非环上的边的两边称为“关键点”,那么关键点将环分成了O(M)段,而每段可以缩成一条边

这样O(QMlogM)可以卡过去

如果询问的点不是关键点,我们可以把它所在的边拆开,仍然是O(M)

具体实现时可以拆环为链,把n到1看成环外边,这样可以前缀和

代码

【20181023T3】“新”的家园【虚图】

原文:https://www.cnblogs.com/lstoi/p/9847676.html

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