求无负环无向图至少具有三个节点的最小简单环,考虑最小的简单环 \(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