广度优先搜索讲解
2026-08-20 19:01:28
发布于:浙江
大家好!今天我来讲广度优先搜索了awa
但是我不会讲啊qwq,那只能放几道习题边做边讲了
P2446 [SDOI2010] 大陆争霸
哇!看起来好麻烦……既要尽快到达指定地点自爆,又要等别的机器人破开保护……这怎么做啊!
我们可以进行 次,每次跑一遍最短路,然后对破坏节点的时间取个max,但是这样是 的,过不了啊!
先别急,我们回想一下最短路是怎么求的。
我们开个优先队列,遍历每一条边,如果新的距离小于当前距离,就把它放进优先队列。这样就能保证每次取出来的时间是上升的了。
再看到这道题,就算要对保护节点取max,还是没有打破遍历时间是上升的这个规则。所以,对于每个出队(被破坏)的点,我们可以分别遍历它能到达的点和它所保护的点,如果时间更优了,那么就更新距离并入队。这样就是对的了,时间复杂度也做到了 。
这题真好玩!
P4366 [Code+#4] 最短路
这道题看上去直接优先队列广度优先搜索就行了……但是真的这么简单吗?
重新读一遍题,发现这题的边数高达 !数据范围也是惊人的 TwT
原来的最短路其实就是看它们每一位是否不同,那每两个点连一条边实在太浪费了!
我们可以将点 连向所有只有一位不同的点,这样也可以看它们每一位是否不同,和之前的图等价的,但是边数只有 !
然后就可以开心地优先队列广搜了~~~
P2993 [FJOI2014] 最短路径树问题
题目是给定一张无向图,求出它字典序最小的最短路径树,后面叽里咕噜说一大串听不懂,就不讲啦~
那怎么求字典序最小的最短路径树呢?
我们求出最短路径后,将邻居按编号排序,从1开始dfs,遇到可能是最短路径的边就加入。这样贪心肯定是对的,而且也能保证字典序最小。
老师还讲了P2934和P6545,但是我太弱了听不懂……
P9370 [APIO2023] 赛博乐园 / cyberland
对于时间可以无限次消成 的点,那先到达这个点然后再去终点和以它为源点去终点没有区别,所以可以一起加入源点广搜。
那么对于时间减半的点呢?最多只能用 次,感觉有点不太好做……
这时候,就要用到,大名鼎鼎的,分层图最短路!
将图分为 层,使用能力相当于往上走一层,这么建图和DP一样,没有后效性,也就是不会影响之前的点。
这样,我们就有了 的做法,但是 啊……
我们发现,当 很大的时候,前面的时间就算很长,也相当于消成没有了!所以我们只要找到这个临界点,大概是 ,对 取个min就行了!
P2865 [USACO06NOV] Roadblocks G
最短路都很好做,直接优先队列广搜就行了。但是次短路呢?为什么会有人研究第二短的路啊!!!
但其实也不算太难,在最短路的基础上稍微改改就行了。
具体来说,就是再开一个数组记录最短路,对于当前队列,如果有一条边更优,那它就成为最短路,原先的最短路成为次短路;否则它就和次短路比较qwq
但是!这里就不能标记vis了!因为有可能这个时候它的次短路还没更新完!这时,我们的剪枝就得改成当前距离小于当前次短路了。这样,由于可以来回走,每个点最多会被松弛两次(最坏情况第二次是从自己往返走一条边回来),时间复杂度是 不变。
P2371 [国家集训队] 墨墨的等式
啊?这题不是解方程吗???
看到这里,你或许也会有和我一样的疑惑。
但是,这和普通的多元一次方程有个不一样的地方,就是它的所有 都是非负的!
怎么做呢?感觉好难啊/O0O\
有个非常神奇的做法,就是选 ,把其它的都模上它,然后发现我们只要枚举 ,看满足其它 之和模这个 等于 ,并且 的和最小的情况就行了!
具体地,我们可以将点 连向 ,权值为 的边,跑一遍优先队列广搜就行了。
但是再次观察我们发现,并不需要广搜!每个 建边都会形成若干个环,随便找一个点照着环跑两圈更新最短路就可以了!
这样,复杂度就是 的。
P9140 [THUPC 2023 初赛] 背包
这……不是背包吗?
但是 这么大……感觉dp不动啊QAQ
我们想一下有没有什么好方法可以缩小范围?
最优解肯定是使劲选一个物品,那这个物品是什么呢?显然是性价比最高的啦~
假设性价比最高的物品是 。
那其他的物品呢?
其实,可以当成上面的问题做, 当成 , 当成权值,跑最长路。只不过,如果连向超过的边,要减去 。
然后,按照我上面说的跑两圈就可以 解决了 awa
Cashier Employment POJ - 1275
设 为 点时需要雇佣的人。
然后我们会发现题目的限制要转成 ,式子看起来太多了,怎么办?
说句闲话,帅童在这里卡住了,哈哈。
我们可以充分发扬人类智慧,开个 记录 到 的和,这样,就转化成 了!
当然,如果 ,要反着算:。但是这三个项,还是太多了!
没事,我们最终求的是 的最小值,所以只需要二分 的值 ,判断可不可以就行了。
然后再加上 的限制 ,以及 ,就可以了,为什么?
因为我们发现列的式子都满足 ,这个和最短路的 很像,所以按要求建图跑最短路(如果有的话)就能求出解了!
当然,因为边权有负的,所以应该跑不能用优先队列的 vis 标记也要打 次的那个广搜。而且图很小,所以能过。
这样子是 的。
全部评论 7
- 置顶
终于更完了qwq
1周前 来自 浙江
0


1周前 来自 浙江
0
老 叟 戏 帅 童
1周前 来自 浙江
2



1周前 来自 浙江
0
您怎么这么强
6天前 来自 美国
0有没有人看啊?
1周前 来自 浙江
0P2934和P6545可以发给我看一下吗,我看看我能不能看懂
1周前 来自 广东
0你可以看题解……
1周前 来自 浙江
0洛谷上的
1周前 来自 浙江
0
建议再加上伪代码
1周前 来自 广东
0我太懒了……但以后会补上的

1周前 来自 浙江
0伪代码其实没啥用,不如直接放真代码
6天前 来自 美国
0
qwq
1周前 来自 浙江
0


























有帮助,赞一个