最小环

[Ir1d]

https://oi-wiki.org/graph/min-circle/

[wmq12138]

最小环用Dijkstra求的时候也可以枚举从1到n枚举s，用dij求解s的单元最短路径，把与s相连的点更新之后，再把d[s]设成inf，这样当s再一次被取出的时候，d[s]就是经过s的最小环长度，这样做是O(n(n+m)logn)的

[Glad-hack]

可以用dfs跑最小环吗？

[Meng118]

受教了

[Wisdommmmmmmm]

@wmq12138
最小环用Dijkstra求的时候也可以枚举从1到n枚举s，用dij求解s的单元最短路径，把与s相连的点更新之后，再把d[s]设成inf，这样当s再一次被取出的时候，d[s]就是经过s的最小环长度，这样做是O(n(n+m)logn)的
“把与s相连的点更新之后，再把d[s]设成inf”这句话的意思是与s相连的点都至少被更新一次的时候吗？还有，这样难道不会把二元环更新到答案吗？

[StephenZhao1]

我觉得可以这样做，先用dfs找到所有的环，
[1, 2,5,6,1]
[2,3,4,5,2]
[1,2,3,4,5,6,1]
怎么排除[1,2,3,4,5,6,1]呢？
因为2-5相连，所以可以排除，只允许严格的前后相连，1-2,2-5,5-6,6-1这样子

[StephenZhao1]

如果是求一个无向有环图里面所有的小环呢？

里面出现点要是顺时针或者逆时针，出现顺序可以不一定，但是不能乱序

[AC-Stray]

GDOI 的题哪里可以交啊

[creating001]

如果图上的点有点权, 那怎么求最短路呀.

[hhhh531889330]

其实还有一种复杂度比较优秀的方法，不难发现最小环一定是一个简单环，
考虑先建出一颗dfs树，然后求出每个点到根的距离，
对于每条返祖边或横插边，可以用lca快速求这个环的大小，直接实现lca是O(nlogn)的，但用四毛子算法可以做到O(n)
因此总复杂度可以做到O(q(n+m))

[hhhh531889330]

好吧，其实有点问题

[369Pai]

注意看例题，它提供了包含每个点最小环大小的两种求法：Floyd + 线段树分治；Dijkstra + 最短路树。即提供 Dijkstra 的 $O(n(n+m)\log n)$ 的全局最小环。

[369Pai]

可交的例题（弱化版）：https://codeforces.com/gym/100917/problem/F