最小环

给定一张图，求边权和最小的简单环的大小。

无向图或者有向图都可以做，需要注意的是无向图直接转成有向图会得到不合法的重边二元环。

以下讨论用 \(n, m\) 分别表示图的点数和边数，为了方便，只讨论简单无向图，其他情况不难扩展。

并且只考虑边权非负的情况。

一般解法

对于一般图，可以使用 Floyd 算法。这里要利用到 Floyd 算法的一个性质，最外层循环枚举松弛 点 \(K\) 更新后，最短路数组 \(dis_{u, v}\) 的值实际上是 \(u\) 到 \(v\) （不包括 \(u, v\) ）仅经过 编号在 \([1, k]\) 中的点的最短路。

根据以上性质，在 Floyd 使用点 \(k\) 松弛之前，枚举所有小于 k 的 \(dis_{i, j}\) 即可求出以 \(k\) 为最大编号节点的最小环大小。

稀疏图做法

对于图较为稀疏的情况，即 \(O(n) \le O(m) < O(n^2)\) ，存在更优秀的解法，可以求出数组 \(f\) ，其中 \(f_u\) 表示包含 \(u\) 节点的最小的环的长度。

考虑计算 \(f_u\) ，以 \(u\) 为根，建出一颗最短路树，然后枚举非树边 \((x, y)\) ，满足 \(lca(x, y) = u\) ， 对于所有这样的非树边，有 \(f_u = min\{dis_x + len_{x, y} + dis_y\}\) 。

总复杂度 \(O(n m \log n)\) ，如果边权很小，最大为 \(W\) ，可以 bfs 求短路，复杂度 \(O(nmW)\) 。

如果只要单次求 \(f_u\) ，这个做法也很合适，复杂度可以少一个 \(n\) 。

还有一个很有意思的单次求 \(f_u\) 的做法，把与 \(u\) 相连的点二进制分组，然后对于每一个划分方式跑多源最短路， 复杂度 \(O(m \log n \log D)\) 或 \(O(m W \log D)\) ，其中 \(D\) 是 \(u\) 的度数。