跳转至

最小环

引入

问题

给出一个图，问其中的由 个节点构成的边权和最小的环 是多大。

图的最小环也称围长。

过程

暴力解法

设 和 之间有一条边长为 的边， 表示删除 和 之间的连边之后， 和 之间的最短路。

那么无向图中的最小环是 。

注意若是在有向图中求最小环，相对应的公式要修改，最小环是 。

总时间复杂度 。

Dijkstra

相关链接：最短路/Dijkstra

过程

枚举所有边，每一次求删除一条边之后对这条边的起点跑一次 Dijkstra，道理同上。

性质

时间复杂度 。

Floyd

相关链接：最短路/Floyd

过程

记原图中 之间边的边权为 。

我们注意到 Floyd 算法有一个性质：在最外层循环到点 时（尚未开始第 次循环），最短路数组 中， 表示的是从 到 且仅经过编号在 区间中的点的最短路。

由最小环的定义可知其至少有三个顶点，设其中编号最大的顶点为 ，环上与 相邻两侧的两个点为 ，则在最外层循环枚举到 时，该环的长度即为 。

故在循环时对于每个 枚举满足 的 ，更新答案即可。

性质

时间复杂度：

实现

下面给出 C++ 的参考实现：

int val[MAXN + 1][MAXN + 1];  // 原图的邻接矩阵

int floyd(const int &n) {
  static int dis[MAXN + 1][MAXN + 1];  // 最短路矩阵
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) dis[i][j] = val[i][j];  // 初始化最短路矩阵
  int ans = inf;
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        ans = std::min(ans, dis[i][j] + val[i][k] + val[k][j]);  // 更新答案
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        dis[i][j] = std::min(
            dis[i][j], dis[i][k] + dis[k][j]);  // 正常的 floyd 更新最短路矩阵
  }
  return ans;
}

val = [[0 for i in range(MAXN + 1)] for j in range(MAXN + 1)]  # 原图的邻接矩阵


def floyd(n):
    dis = [[0 for i in range(MAXN + 1)] for j in range(MAXN + 1)]  # 最短路矩阵
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            dis[i][j] = val[i][j]  # 初始化最短路矩阵
    ans = inf
    for k in range(1, n + 1):
        for i in range(1, k):
            for j in range(1, i):
                ans = min(ans, dis[i][j] + val[i][k] + val[k][j])  # 更新答案
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dis[i][j] = min(
                    dis[i][j], dis[i][k] + dis[k][j]
                )  # 正常的 floyd 更新最短路矩阵
    return ans

例题

GDOI2018 Day2 巡逻

给出一张 个点的无负权边无向图，要求执行 个操作，三种操作

  1. 删除一个图中的点以及与它有关的边
  2. 恢复一个被删除点以及与它有关的边
  3. 询问点 所在的最小环大小

对于 的数据，有

对于每一个点 所在的简单环，都存在两条与 相邻的边，删去其中的任意一条，简单环将变为简单路径。

那么枚举所有与 相邻的边，每次删去其中一条，然后跑一次 Dijkstra。

或者直接对每次询问跑一遍 Floyd 求最小环，

对于 的数据，有 。

还是利用 Floyd 求最小环的算法。

若没有删除，删去询问点将简单环裂开成为一条简单路。

然而第二步的求解改用 Floyd 来得出。

那么答案就是要求出不经过询问点 的情况下任意两点之间的距离。

怎么在线？

强行离线，利用离线的方法来避免删除操作。

将询问按照时间顺序排列，对这些询问建立一个线段树。

每个点的出现时间覆盖所有除去询问该点的时刻外的所有询问，假设一个点被询问 次，则它的出现时间可以视为 段区间，插入到线段树上。

完成之后遍历一遍整棵线段树，在经过一个点时存储一个 Floyd 数组的备份，然后加入被插入在这个区间上的所有点，在离开时利用备份数组退回去即可。

这个做法的时间复杂度为 。

还有一个时间复杂度更优秀的在线做法。

对于一个对点 的询问，我们以 为起点跑一次最短路，然后把最短路树建出来，顺便处理出每个点是在 的哪棵子树内。

那么一定能找出一条非树边，满足这条非树边的两个端点在根的不同子树中，使得这条非树边 两个端点到根的路径就是最小环。

证明：

显然最小环包含至少两个端点在根的不同子树中一条非树边。

假设这条边为 ，那么最短路树上 到 的路径是所有 到 的路径中最短的那条， 到 的路径也是最短的那条，那么 这个环肯定不会比最小环要长。

那么就可以枚举所有非树边，更新答案。

每次询问的复杂度为跑一次单源最短路的复杂度，为 。

总时间复杂度为 。

最后更新: 2024年10月9日
创建日期: 2018年7月11日
回到页面顶部