牛客周赛 Round 54F 出题人题解

大家好，这里是牛客周赛 Round 54的组题人兼A、F出题人。希望大家喜欢清楚姐姐与竹鼠的故事~

根据我出题一题多解的惯例，在这里分享一下F题的两个 std 做法：

分治爆搜

2024.08.25 Update：该做法复杂度理论是错误的，但本题中恰好可以通过，请仔细甄别。感谢 @summ3r 同学的指正。

您好，牛客周赛Round 54的F的分治爆搜做法有误，用下列数据可以卡TLE。但是卡的是搜索方向为上左下右的代码，对于std代码的搜索顺序上左右下受题目限制十分难卡，如果std把queue换成stack或终点不是(n,m)等将会好卡。但无论如何该做法应当也是错误的。

使用到了类似于分治的思想。使用一遍 dfs 搜索出一条可行路径后，对于路径上全部的点入栈、扩展搜索，各自跑 dfs ，如果能到达另一个路径上的点，则将新的这条路径上的全部点入栈、扩展搜索。

该做法细节较多，特别在于回溯部分。最终每个点至多搜索一次，复杂度 ，由于跑了好几次，可能常数稍大。

参考代码 。

点双/圆方树

对于一个点双中的两点，它们之间简单路径的并集，恰好完全等于这个点双。即同一个点双中的两不同点 之间一定存在一条简单路径经过给定的在同一个点双内的另一点 。

圆方树模板题，或者连接起点和终点后跑点双缩点，复杂度 。

参考代码可见 thisislike_fan 的这份提交。

另外，关于为什么一定要使用点双，而边双无法通过，这里提供一个参考样例：