跳转至

最小环

引入

问题

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

图的最小环也称围长。

过程

暴力解法

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

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

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

总时间复杂度 。

Dijkstra

相关链接：最短路/Dijkstra

过程

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

性质

时间复杂度 。

Floyd

相关链接：最短路/Floyd

过程

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

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

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

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

记录路径

现在已经知道了环的形式为 ，然后再从 回到 （经过的点编号均 ）。

问题转化为求 的路径。由三角不等式 ，考虑记录 表示使得 的点。显然 就在 的路径上。

于是可以将路径转化为 和 两段，分别递归处理即可。

证明递归不会陷入死循环

使用反证法。

假设环会重复经过一个点 ，那么环上必然会有一条 出发经过若干条边回到 的边。这就构成了一个新的环。

由于图中不会出现负环（如果出现负环就不会有最小环了），所以新环的边权和必然是小于等于原环的。

所以只需要截取这一个环，那么就不会重复经过一个点 ，假设不成立，故环不会重复经过一个点。

所以当递归到 两点时，其 必然不等于两点编号，也就是新加入了一个点。

特别地，当 和 相邻时，直接返回即可。

由于总点数为 ，那么新加入的次数（即递归次数）不会超过 ，因此递归不会陷入死循环。

性质

时间复杂度：。

实现

下面给出 C++ 和 Python 的参考实现（记录路径）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 图的点数为 n
int val[MAXN + 1][MAXN + 1];  // 原图的邻接矩阵
int cnt, path[MAXN + 5];      // 记录最小环的路径和长度

void get_path(int u, int v) {  // 获得 u 到 v 之间的路径
  if (pos[u][v] == 0) return;

  int k = pos[u][v];
  get_path(u, k);
  path[++cnt] = k;
  get_path(k, v);
}

void Floyd(const int &n) {
  static int dis[MAXN + 1][MAXN + 1];  // 最短路矩阵
  static int pos[MAXN + 1][MAXN + 1];
  memcpy(dis, val, sizeof(val));
  memset(pos, 0, sizeof(pos));
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        if (ans >
            (long long)val[i][k] + val[k][j] + dis[i][j]) {  // 发现了更短的环
          // 由于这里保证了 j<i<k，所以三个点不同，不会出现零环。
          ans = val[i][k] + val[k][j] + dis[i][j], cnt = 0;
          path[++cnt] = i, path[++cnt] = k,
          path[++cnt] = j;  // 依次加入 i,k,j 三点
          get_path(j, i);   // 加入 j 到 i 的路径
        }

    for (int i = 1; i <= n; ++i)  // 正常 Floyd 更新最短路
      for (int j = 1; j <= n; ++j) {
        if (dis[i][j] > dis[i][k] + dis[k][j]) {
          dis[i][j] = dis[i][k] + dis[k][j];
          pos[i][j] = k;  // 当前路径可以由 k 更新得到
        }
      }
  }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# 定义一个足够大的值表示无穷大
INF = sys.maxsize


def get_path(i, j, pos, path, cnt):
    """
    递归地获取从节点 i 到节点 j 的最短路径上的中间节点。

    Args:
        i (int): 起始节点 (0-based index).
        j (int): 结束节点 (0-based index).
        pos (list[list[int]]): 记录最短路径中间节点的矩阵. pos[i][j] = k 表示从 i 到 j 的最短路径经过 k.
        path (list[int]): 存储路径节点的列表 (使用 0-based index).
        cnt (int): 当前路径节点的数量.

    Returns:
        int: 更新后的路径节点数量.
    """
    # 如果 pos[i][j] 为 -1，表示 i 到 j 没有中间节点
    if pos[i][j] == -1:
        return cnt

    # 获取中间节点 k
    k = pos[i][j]
    # 递归获取 i 到 k 的路径
    cnt = get_path(i, k, pos, path, cnt)
    # 将中间节点 k 加入路径
    path[cnt] = k
    cnt += 1
    # 递归获取 k 到 j 的路径
    cnt = get_path(k, j, pos, path, cnt)
    return cnt


def find_minimum_cycle_undirected(n, edges):
    """
    使用 Floyd-Warshall 算法查找无向图中的最小环。

    Args:
        n (int): 图的节点数 (1 到 n).
        edges (list[tuple]): 边的列表，每个元素是 (u, v, w)，表示节点 u 和 v 之间有一条权重为 w 的边。
                             节点索引是 1 到 n。

    Returns:
        tuple: 包含最小环的长度和路径。
               如果不存在环，返回 (INF, []).
               路径是一个节点索引列表 (1-based index)。
    """
    # 内部使用 0-based indexing
    N = n
    # 初始化邻接矩阵 g，表示原始边的权重
    g = [[INF for _ in range(N)] for _ in range(N)]
    # 初始化最短路矩阵 dis，开始时与 g 相同
    dis = [[INF for _ in range(N)] for _ in range(N)]
    # 初始化 pos 矩阵，记录最短路径的中间节点
    pos = [[-1 for _ in range(N)] for _ in range(N)]

    # 初始化对角线为 0 (节点到自身的距离)
    for i in range(N):
        g[i][i] = 0
        dis[i][i] = 0

    # 根据输入的边构建邻接矩阵 (无向图)
    for u, v, w in edges:
        # 将 1-based 索引转换为 0-based
        u -= 1
        v -= 1
        # 对于无向图，边是双向的
        g[u][v] = min(g[u][v], w)
        g[v][u] = min(g[v][u], w)
        dis[u][v] = min(dis[u][v], w)
        dis[v][u] = min(dis[v][u], w)

    # 初始化最小环长度为无穷大
    min_cycle_len = INF
    # 初始化最小环路径
    min_cycle_path = []

    # Floyd-Warshall 算法核心部分
    # k 作为中间节点 (0-based index)
    for k in range(N):
        # 在更新 dis[i][j] 之前，检查通过节点 k 是否能形成更小的环
        # 环由 i -> k -> j -> ... -> i 组成
        # 这里的 dis[i][j] 是在考虑节点 0 到 k-1 作为中间节点时的最短路径
        # C++ 代码中使用 i < k 和 j < i 的循环顺序，这里也遵循这个逻辑 (0-based)
        for i in range(k):  # 0 <= i < k
            for j in range(i):  # 0 <= j < i
                # 检查 i, k, j 是否构成一个环，并且通过 dis[i][j] 连接
                # 确保原始边 g[i][k] 和 g[k][j] 存在 (不为 INF)
                # 并且 i 到 j 的最短路径 dis[i][j] 存在 (不为 INF)
                if g[i][k] != INF and g[k][j] != INF and dis[i][j] != INF:
                    current_cycle_len = g[i][k] + g[k][j] + dis[i][j]
                    if current_cycle_len < min_cycle_len:
                        min_cycle_len = current_cycle_len
                        # 重构路径
                        path = [0] * (N + 5)  # 临时存储路径的数组，长度足够大
                        cnt = 0
                        # 按照 i, k, j 的顺序加入路径
                        path[cnt] = i
                        cnt += 1
                        path[cnt] = k
                        cnt += 1
                        path[cnt] = j
                        cnt += 1
                        # 获取 j 到 i 的最短路径上的中间节点 (使用之前计算的 dis 和 pos)
                        cnt = get_path(j, i, pos, path, cnt)
                        # 提取实际路径节点 (去除未使用的部分)
                        # 将 0-based 索引转换为 1-based
                        min_cycle_path = [node + 1 for node in path[:cnt]]

        # 标准 Floyd-Warshall 更新最短路径
        for i in range(N):
            for j in range(N):
                if (
                    dis[i][k] != INF
                    and dis[k][j] != INF
                    and dis[i][j] > dis[i][k] + dis[k][j]
                ):
                    dis[i][j] = dis[i][k] + dis[k][j]
                    # 记录从 i 到 j 的最短路径经过 k
                    pos[i][j] = k

    return min_cycle_len, min_cycle_path

模板题

AcWing 344 观光之旅

给定一张 个点无向图，求图中一个至少包含 个点的环，环上的节点不重复，并且环上的边的长度之和最小。

该问题称为无向图的最小环问题。

你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

时间复杂度接受 的做法，套用 Floyd 求最小环的做法即可。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <bits/stdc++.h>
using lint = long long;
// 定义一个足够大的常量，用于表示图的最大节点数
const int MAXN = 110;

// 定义一个足够大的值，用于表示无穷大，初始化最小环长度
lint ans = 1e9;  // lint 是 long long 的别名

// 图的节点数 n，边数 m
// cnt 记录最小环路径中的节点数量
// path 存储最小环的路径节点
int n, m, cnt, path[MAXN];

// g 存储原始图的邻接矩阵
// dis 存储最短路径矩阵 (Floyd-Warshall 算法计算过程中更新)
// pos 记录最短路径的中间节点，pos[i][j] = k 表示从 i 到 j 的最短路径经过 k
int g[MAXN][MAXN], dis[MAXN][MAXN], pos[MAXN][MAXN];

// 递归函数：获取从节点 u 到节点 v 的最短路径上的中间节点
// 根据 pos 矩阵重构路径
void get_path(int u, int v) {
  // 如果 pos[u][v] 为 0，表示 u 到 v 没有中间节点，直接返回
  if (pos[u][v] == 0) return;

  // 获取中间节点 k
  int k = pos[u][v];
  // 递归获取 u 到 k 的路径
  get_path(u, k);
  // 将中间节点 k 加入路径
  path[++cnt] = k;
  // 递归获取 k 到 v 的路径
  get_path(k, v);
}

// Floyd-Warshall 算法函数：查找图中的最小环
void Floyd() {
  // 外层循环：k 作为中间节点 (1 到 n)
  for (int k = 1; k <= n; ++k) {
    // 内层循环：i 和 j，用于检查通过节点 k 是否能形成更小的环
    // 这里循环顺序是 i 从 1 到 k-1，j 从 1 到 i-1
    // 这样可以检查由 i -> k -> j -> ... -> i 构成的环
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        // 检查通过节点 k 连接 i 和 j 是否形成更小的环
        // 环的长度是 i 到 k 的原始边权重 g[i][k] + k 到 j 的原始边权重 g[k][j]
        // + i 到 j 的当前最短路径 dis[i][j]
        if (ans > (long long)g[i][k] + g[k][j] + dis[i][j]) {
          // 发现了更小的环
          ans = g[i][k] + g[k][j] + dis[i][j];  // 更新最小环长度
          cnt = 0;                              // 重置路径计数
          // 将 i, k, j 依次加入路径
          path[++cnt] = i, path[++cnt] = k, path[++cnt] = j;
          // 获取 j 到 i 的最短路径上的中间节点，加入路径
          get_path(j, i);
        }

    // 标准 Floyd-Warshall 更新最短路径
    // i 从 1 到 n，j 从 1 到 n
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j) {
        // 如果通过中间节点 k 可以获得更短的从 i 到 j 的路径
        if (dis[i][j] > dis[i][k] + dis[k][j]) {
          // 更新最短路径
          dis[i][j] = dis[i][k] + dis[k][j];
          // 记录从 i 到 j 的最短路径经过 k
          pos[i][j] = k;
        }
      }
  }
}

// 主函数
int main() {
  // 读取节点数 n 和边数 m
  std::cin >> n >> m;
  // 初始化原始邻接矩阵 g，所有边的权重设为无穷大 (0x3f 通常表示一个很大的值)
  memset(g, 0x3f, sizeof(g));
  // 将节点到自身的距离设为 0
  for (int i = 1; i <= n; ++i) g[i][i] = 0;
  // 读取 m 条边，构建原始邻接矩阵 g
  // 对于无向图，边是双向的，取较小的权重
  for (int i = 0, u, v, w; i < m; ++i) {
    std::cin >> u >> v >> w;
    g[u][v] = g[v][u] = std::min(g[u][v], w);
  }
  // 将原始邻接矩阵 g 复制到最短路径矩阵 dis
  memcpy(dis, g, sizeof(g));
  // 调用 Floyd 算法查找最小环
  Floyd();
  // 根据最小环长度判断是否存在环
  if (ans == 1e9) {  // 如果最小环长度仍为无穷大，表示不存在环
    puts("No solution.");
  } else {
    // 如果存在环，打印路径节点
    // std::cout << "ans = " << ans << std::endl; // 打印最小环长度 (注释掉)
    // 打印路径节点，用空格分隔
    for (int i = 1; i <= cnt; ++i)
      std::cout << path[i]
                << (i == cnt ? "" : " ");  // 最后一个节点后面没有空格
    std::cout << std::endl;                // 路径打印完后换行
  }
  return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
import copy
import sys

# 定义一个足够大的值表示无穷大
INF = sys.maxsize


def get_path(i, j, pos, path, cnt):
    """
    递归地获取从节点 i 到节点 j 的最短路径上的中间节点。

    Args:
        i (int): 起始节点 (0-based index).
        j (int): 结束节点 (0-based index).
        pos (list[list[int]]): 记录最短路径中间节点的矩阵. pos[i][j] = k 表示从 i 到 j 的最短路径经过 k.
        path (list[int]): 存储路径节点的列表 (使用 0-based index).
        cnt (int): 当前路径节点的数量.

    Returns:
        int: 更新后的路径节点数量.
    """
    # 如果 pos[i][j] 为 -1，表示 i 到 j 没有中间节点
    if pos[i][j] == -1:
        return cnt

    # 获取中间节点 k
    k = pos[i][j]
    # 递归获取 i 到 k 的路径
    cnt = get_path(i, k, pos, path, cnt)
    # 将中间节点 k 加入路径
    path[cnt] = k
    cnt += 1
    # 递归获取 k 到 j 的路径
    cnt = get_path(k, j, pos, path, cnt)
    return cnt


def find_minimum_cycle_undirected(n, edges):
    """
    使用 Floyd-Warshall 算法查找无向图中的最小环。

    Args:
        n (int): 图的节点数 (1 到 n).
        edges (list[tuple]): 边的列表，每个元素是 (u, v, w)，表示节点 u 和 v 之间有一条权重为 w 的边。
                             节点索引是 1 到 n。

    Returns:
        tuple: 包含最小环的长度和路径。
               如果不存在环，返回 (INF, []).
               路径是一个节点索引列表 (1-based index)。
    """
    # 内部使用 0-based indexing
    N = n
    # 初始化邻接矩阵 g，表示原始边的权重
    g = [[INF for _ in range(N)] for _ in range(N)]
    # 初始化最短路矩阵 dis，开始时与 g 相同
    dis = [[INF for _ in range(N)] for _ in range(N)]
    # 初始化 pos 矩阵，记录最短路径的中间节点
    pos = [[-1 for _ in range(N)] for _ in range(N)]

    # 初始化对角线为 0 (节点到自身的距离)
    for i in range(N):
        g[i][i] = 0
        dis[i][i] = 0

    # 根据输入的边构建邻接矩阵 (无向图)
    for u, v, w in edges:
        # 将 1-based 索引转换为 0-based
        u -= 1
        v -= 1
        # 对于无向图，边是双向的
        g[u][v] = min(g[u][v], w)
        g[v][u] = min(g[v][u], w)
        dis[u][v] = min(dis[u][v], w)
        dis[v][u] = min(dis[v][u], w)

    # 初始化最小环长度为无穷大
    min_cycle_len = INF
    # 初始化最小环路径
    min_cycle_path = []

    # Floyd-Warshall 算法核心部分
    # k 作为中间节点 (0-based index)
    for k in range(N):
        # 在更新 dis[i][j] 之前，检查通过节点 k 是否能形成更小的环
        # 环由 i -> k -> j -> ... -> i 组成
        # 这里的 dis[i][j] 是在考虑节点 0 到 k-1 作为中间节点时的最短路径
        # C++ 代码中使用 i < k 和 j < i 的循环顺序，这里也遵循这个逻辑 (0-based)
        for i in range(k):  # 0 <= i < k
            for j in range(i):  # 0 <= j < i
                # 检查 i, k, j 是否构成一个环，并且通过 dis[i][j] 连接
                # 确保原始边 g[i][k] 和 g[k][j] 存在 (不为 INF)
                # 并且 i 到 j 的最短路径 dis[i][j] 存在 (不为 INF)
                if g[i][k] != INF and g[k][j] != INF and dis[i][j] != INF:
                    current_cycle_len = g[i][k] + g[k][j] + dis[i][j]
                    if current_cycle_len < min_cycle_len:
                        min_cycle_len = current_cycle_len
                        # 重构路径
                        path = [0] * (N + 5)  # 临时存储路径的数组，长度足够大
                        cnt = 0
                        # 按照 i, k, j 的顺序加入路径
                        path[cnt] = i
                        cnt += 1
                        path[cnt] = k
                        cnt += 1
                        path[cnt] = j
                        cnt += 1
                        # 获取 j 到 i 的最短路径上的中间节点 (使用之前计算的 dis 和 pos)
                        cnt = get_path(j, i, pos, path, cnt)
                        # 提取实际路径节点 (去除未使用的部分)
                        # 将 0-based 索引转换为 1-based
                        min_cycle_path = [node + 1 for node in path[:cnt]]

        # 标准 Floyd-Warshall 更新最短路径
        for i in range(N):
            for j in range(N):
                if (
                    dis[i][k] != INF
                    and dis[k][j] != INF
                    and dis[i][j] > dis[i][k] + dis[k][j]
                ):
                    dis[i][j] = dis[i][k] + dis[k][j]
                    # 记录从 i 到 j 的最短路径经过 k
                    pos[i][j] = k

    return min_cycle_len, min_cycle_path


# --- 主程序入口 ---
if __name__ == "__main__":
    # 读取节点数 n 和边数 m
    n, m = map(int, sys.stdin.readline().split())

    # 读取边信息
    edges = []
    for _ in range(m):
        u, v, w = map(int, sys.stdin.readline().split())
        edges.append((u, v, w))

    # 查找最小环
    min_len, path = find_minimum_cycle_undirected(n, edges)

    # 输出结果
    if min_len == INF:
        print("No solution.")
    else:
        # 打印路径节点 (1-based index)，用空格分隔
        print(" ".join(map(str, path)))

例题 2

GDOI2018 Day2 巡逻

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

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

对于 的数据，有

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

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

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

对于 的数据，有 。

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

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

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

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

怎么在线？

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

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

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

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

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

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

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

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

证明：

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

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

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

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

总时间复杂度为 。

本页面最近更新：2025/5/10 21:03:59，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：cesonic, Doubeecat, Early0v0, Enter-tainer, GoodCoder666, greyqz, iamtwz, Ir1d, ksyx, Marcythm, Menci, PeterlitsZo, shawlleyw, sshwy, sun2snow, Tiphereth-A, u5n, ywwywwyww
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用