求无负环无向图至少具有三个节点的最小简单环，考虑最小的简单环 \(x_1x_2x_3\cdots x_nx_1,n\ge 3\)，不妨令 \(x_n=max\{x_i\}\)，那么显然有 \(x_1x_2\cdots x_{n-1}\) 是只经过 \([1,x_n)\) 间节点的最短路，因此当 floyd 更新到 \(x_n-1\) 时，枚举 \((u,v)\in[1,x_n)^2\)，则有 \(x_nPath(u,v)x_n\) 是一个合法的环，并且总会枚举到该图的最小环。有向图同理，复杂度 \(O(n^3)\)。
又或者可以每次删除一条边跑最短路，复杂度 \(O(m(ShortestPath))\)
标签：1x,复杂度,最小,Trick,cdots,枚举 From： https://www.cnblogs.com/watware-cym/p/17221092.html