最小环
引入
问题
给出一个图，问其中的由 𝑛n
个节点构成的边权和最小的环 (𝑛 ≥3)(n≥3) 是多大．
图的最小环也称围长．
过程
暴力解法
设 𝑢u 和 𝑣v 之间有一条边长为 𝑤w 的边，𝑑𝑖𝑠(𝑢,𝑣)dis(u,v) 表示删除 𝑢u 和 𝑣v 之间的连边之后，𝑢u 和 𝑣v 之间的最短路．
那么无向图中的最小环是 𝑑𝑖𝑠(𝑢,𝑣) +𝑤dis(u,v)+w．
注意若是在有向图中求最小环，相对应的公式要修改，最小环是 𝑑𝑖𝑠(𝑣,𝑢) +𝑤dis(v,u)+w．
总时间复杂度 𝑂(𝑛2𝑚)O(n2m)．
Dijkstra
相关链接：最短路/Dijkstra
过程
枚举所有边，每一次求删除一条边之后对这条边的起点跑一次 Dijkstra，道理同上．
性质
时间复杂度 𝑂(𝑚(𝑛 +𝑚)log𝑛)O(m(n+m)logn)．
Floyd
相关链接：最短路/Floyd
过程
记原图中 𝑢,𝑣u,v 之间边的边权为 𝑣𝑎𝑙(𝑢,𝑣)val(u,v)．
我们注意到 Floyd 算法有一个性质：在最外层循环到点 𝑘k 时（尚未开始第 𝑘k 次循环），最短路数组 𝑑𝑖𝑠dis 中，𝑑𝑖𝑠𝑢,𝑣disu,v 表示的是从 𝑢u 到 𝑣v 且仅经过编号在 [1,𝑘)[1,k) 区间中的点的最短路．
由最小环的定义可知其至少有三个顶点，设其中编号最大的顶点为 𝑤w，环上与 𝑤w 相邻两侧的两个点为 𝑢,𝑣u,v，则在最外层循环枚举到 𝑘 =𝑤k=w 时，该环的长度即为 𝑑𝑖𝑠𝑢,𝑣 +𝑣𝑎𝑙(𝑣,𝑤) +𝑣𝑎𝑙(𝑤,𝑢)disu,v+val(v,w)+val(w,u)．
故在循环时对于每个 𝑘k 枚举满足 𝑖 <𝑘,𝑗 <𝑘i<k,j<k 的 (𝑖,𝑗)(i,j)，更新答案即可．
记录路径
现在已经知道了环的形式为 𝑢 →𝑘 →𝑣u→k→v，然后再从 𝑣v 回到 𝑢u（经过的点编号均 <𝑘<k）．
问题转化为求 𝑣 ⇝𝑢v⇝u 的路径．由三角不等式 𝑑𝑖𝑠𝑢,𝑣 ≤𝑑𝑖𝑠𝑢,𝑖 +𝑑𝑖𝑠𝑖,𝑣disu,v≤disu,i+disi,v，考虑记录 𝑝𝑜𝑠𝑢,𝑣 =𝑗posu,v=j 表示使得 𝑑𝑖𝑠𝑢,𝑣 =𝑑𝑖𝑠𝑢,𝑗 +𝑑𝑖𝑠𝑗,𝑣disu,v=disu,j+disj,v 的点．显然 𝑗j 就在 𝑣 ⇝𝑢v⇝u 的路径上．
于是可以将路径转化为 𝑣 ⇝𝑗v⇝j 和 𝑗 ⇝𝑢j⇝u 两段，分别递归处理即可．
证明递归不会陷入死循环
使用反证法．
假设环会重复经过一个点 𝑢u，那么环上必然会有一条 𝑢u 出发经过若干条边回到 𝑢u 的边．这就构成了一个新的环．
由于图中不会出现负环（如果出现负环就不会有最小环了），所以新环的边权和必然是小于等于原环的．
所以只需要截取这一个环，那么就不会重复经过一个点 𝑢u，假设不成立，故环不会重复经过一个点．
所以当递归到 𝑢,𝑣u,v 两点时，其 𝑝𝑜𝑠𝑢,𝑣posu,v 必然不等于两点编号，也就是新加入了一个点．
特别地，当 𝑢u 和 𝑣v 相邻时，直接返回即可．
由于总点数为 𝑛n，那么新加入的次数（即递归次数）不会超过 𝑛n，因此递归不会陷入死循环．
性质
时间复杂度：𝑂(𝑛3)O(n3)．
实现
下面给出 C++ 和 Python 的参考实现（记录路径）：
C++Python
---|---
---|---
模板题
给定一张 𝑛n 个点无向图，求图中一个至少包含 33 个点的环，环上的节点不重复，并且环上的边的长度之和最小．
该问题称为无向图的最小环问题．
你需要输出最小环的方案，若最小环不唯一，输出任意一个均可．
𝑛 ≤100n≤100
时间复杂度接受 𝑂(𝑛3)O(n3) 的做法，套用 Floyd 求最小环的做法即可．
C++Python
---|---
---|---
例题 2
GDOI2018 Day2 巡逻
给出一张 𝑛n 个点的无负权边无向图，要求执行 𝑞q 个操作，三种操作
- 删除一个图中的点以及与它有关的边
- 恢复一个被删除点以及与它有关的边
- 询问点 𝑥x 所在的最小环大小
对于 50%50% 的数据，有 𝑛,𝑞 ≤100n,q≤100
对于每一个点 𝑥x 所在的简单环，都存在两条与 𝑥x 相邻的边，删去其中的任意一条，简单环将变为简单路径．
那么枚举所有与 𝑥x 相邻的边，每次删去其中一条，然后跑一次 Dijkstra．
或者直接对每次询问跑一遍 Floyd 求最小环，𝑂(𝑞𝑛3)O(qn3)
对于 100%100% 的数据，有 𝑛,𝑞 ≤400n,q≤400．
还是利用 Floyd 求最小环的算法．
若没有删除，删去询问点将简单环裂开成为一条简单路．
然而第二步的求解改用 Floyd 来得出．
那么答案就是要求出不经过询问点 𝑥x 的情况下任意两点之间的距离．
怎么在线？
强行离线，利用离线的方法来避免删除操作．
将询问按照时间顺序排列，对这些询问建立一个线段树．
每个点的出现时间覆盖所有除去询问该点的时刻外的所有询问，假设一个点被询问 𝑥x 次，则它的出现时间可以视为 𝑥 +1x+1 段区间，插入到线段树上．
完成之后遍历一遍整棵线段树，在经过一个点时存储一个 Floyd 数组的备份，然后加入被插入在这个区间上的所有点，在离开时利用备份数组退回去即可．
这个做法的时间复杂度为 𝑂(𝑞𝑛2log𝑞)O(qn2logq)．
还有一个时间复杂度更优秀的在线做法．
对于一个对点 𝑥x 的询问，我们以 𝑥x 为起点跑一次最短路，然后把最短路树建出来，顺便处理出每个点是在 𝑥x 的哪棵子树内．
那么一定能找出一条非树边，满足这条非树边的两个端点在根的不同子树中，使得这条非树边 ++ 两个端点到根的路径就是最小环．
证明：
显然最小环包含至少两个端点在根的不同子树中一条非树边．
假设这条边为 (𝑢,𝑣)(u,v)，那么最短路树上 𝑥x 到 𝑢u 的路径是所有 𝑥x 到 𝑢u 的路径中最短的那条，𝑥x 到 𝑣v 的路径也是最短的那条，那么 𝑥 →𝑢 →𝑣 →𝑥x→u→v→x 这个环肯定不会比最小环要长．
那么就可以枚举所有非树边，更新答案．
每次询问的复杂度为跑一次单源最短路的复杂度，为 𝑂(𝑛2)O(n2)．
总时间复杂度为 𝑂(𝑞𝑛2)O(qn2)．
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, Tiphereth-A, ywwywwyww, Enter-tainer, greyqz, iamtwz, ksyx, c-forrest, cesonic, Doubeecat, Early0v0, GoodCoder666, Marcythm, Menci, PeterlitsZo, shawlleyw, sshwy, sun2snow, u5n, Xeonacid, ZnPdCo 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用