首页 > 其他分享 >关于单位权图最短路的一些小思考

关于单位权图最短路的一些小思考

时间:2023-09-12 17:57:03浏览次数:42  
标签:set 标记 短路 边集 leq 权图 思考

关于单位权图最短路的一些小思考

单位权图

每条边权值都为 \(1\) (或者全部相同也行)的图。

最短路

显然,单位全图的最短路不会经过同一个点,所以,跑单位权图的最短路要用 BFS

所以我们得到一个处理单位全图的性质 \(1\) :用一个标记数组取标记哪个点有没有被走过,如果没有就标记并加入到队列,有显然就跳过。

优化

我们要考虑几种情况:

\(n\) 和 \(m\) 都是正常数据

直接像上面一样跑。

\(n\) 正常,\(m\) 很大

如 \(1\leq n\leq 10^5,1\leq m\leq \frac{n(n+1)}{2}\)

例题:ABC319G

因为 \(m\) 很大,所以给的是反图。这种请况我们把标记数组改为 \(set\)(链表也行) ,边集也改为 \(set\)。

这样在跑图时可以遍历标记 \(set\) 并判断有没有在边集 \(set\) 里出现,这样有什么好处?

数组标记时,每次遍历都是 \(O(n)\) 的,但是 \(set\) 可以支持删除和 \(O(size)\) 遍历,反图边很少,所以复杂度很少。

\(n\) 和 \(m\) 都很小,但是要跑很多遍

如 \(1\leq n,m\leq 2000\),要跑 \(n\) 次最短路。

我们将 \(set\) 改为 \(bitset\) ,判断标记 \(set\) 并判断有没有在边集 \(set\) 里出现,在 \(bitset\) 就是两个取 \(and\),遍历复杂度更小,且判断少一个 \(log\)。

总结

  1. 用一个标记数组取标记哪个点有没有被走过,如果没有就标记并加入到队列,有显然就跳过。

  2. 对于一些情况,标记和边集改为 \(set\),可优化复杂度。

标签:set,标记,短路,边集,leq,权图,思考
From: https://www.cnblogs.com/sunzz3183/p/17697395.html

相关文章

  • 系统熵增是怎么产生的?————数据对象模型里添加属性欠思考
    熵增定律指出,在没有外力作用下的封闭系统中,熵(或混乱度)总是增加的。就是说,任何封闭系统中、在没有外力作用下,都会陷入混乱。屋子不收拾会变乱;人不自律会懒散;生活不规律或无节制,人就会出现健康问题;同样,对于我们的信息系统,一旦缺乏规范和管控,就会越来越难于迭代和维护。这些例子......
  • 封装的思考(快捷键Alt+insert很重要,千万记住,它还能构造函数)
      这边就是封装的意义,然后操作方式和C++没差多少 然后这里是java封装的语法,看看和C++的区别 接着就是一些快捷键的使用  ......
  • 在公司学习日,学习了结构思考力
    大家好,我是Edison。近日,在公司的学习日上,学习了李忠秋老师的在线直播课《结构思考力》,虽然只有短短的一小时内容,但却令我印象深刻,以至于我开始逐渐刻意训练自己的结构化思维。所谓的《结构思考力》核心内容其实来源于一本经典的书籍巴巴拉·明托的《金字塔原理》,我老早就听说过,......
  • 函数重载的思考
    这个就是说,函数重载除了可以变量类型有差别外,输入的变量个数也可以有差别然后这张图就是说,还可以把强制转换用到重载函数里头(如果上面只要int,而下面的函数构造只有double的话)......
  • 最短路
    dijkstra(好像有问题)单源最短路,原理比较简单,就是贪心。每次选取最近的边(没选过),用它去更新其他的。传统做法是每次扫一遍寻找最近的遍,其实可以用堆优化。voiddijkstra(ints){q.push(JCY{s,0});for(inti=1;i<=n+n;i++){num[i]=0x3f3f3f3f;//有因为最......
  • 独特角度与思考方式:创造与众不同的内容灵感
    嘿,小红书的朋友们!今天我要和大家分享一些关于创造与众不同的内容灵感的独特角度和思考方式。我们都知道,要在这个信息爆炸的时代脱颖而出,需要提供令人印象深刻且与众不同的内容。那么,让我们来探索一些方法,如何以独特的思维方式寻找创意灵感吧!1.沉浸自己,引发灵感想要创造与众不......
  • 专访 UIUC 李博 | 从可用到可信,学界对 AI 的终极思考
    本文首发自HyperAI超神经微信公众平台~ChatGPT的出现让AI再次引起了一场科技圈的震动,这场震动影响深远,让科技界分为两派。一派认为,AI迅速发展可能会在不久后取代人类,这种「威胁论」虽然不无道理,但另一派也提出不同观点,AI的智力水平依然尚未赶超人类甚至「还不如狗」,距离危......
  • 近期对于市场的一些思考
    先说结论,我依旧维持在2022年判断,最晚24年年中我们应该能迎来一波牛市,理由非常简单粗暴:周期已至,所有资产的价格几乎都在底部(包括房子,股票,期权),而糟糕的经济状况以及频繁出现的救市政策无不表明现在的一切现状都已经烂透了。但是就是这样的一个环境,意味着我们需要在此时......
  • 关于博客园最近情况的一些思考
    今天回到家,我在犇犇中偶然得知博客园要倒了,原因是资金不足。博客园作为一个没有广告的网址,我觉得很赞,但是这也直接导致了博客园的收益很小。博客园能走到现在都是一个奇迹,它能不能接续走下去,取决于大家的支持,所以,充会员吧!这是对博客园的唯一支持。博客园的唯一收入来源好像就是......
  • 最短路
    基本算法:\(dijkstra\)使用条件:无负权边每次取出还未取出过的\(dis\)最小的节点更新其他节点正确性证明:因为是\(dis\)最小的节点,别的节点不可能有一条路径走到这个节点且\(dis\)更小(路径为正)stl-pq默认是大根堆,用负号处理为小根堆intn,m,s,tot;inthead[N],ver[M......