最小环

YZY Lv3
  2025-06-16 23:53:39 2025-06-16 23:53:39 Created   2025-06-16 23:53:39 2025-06-16 23:53:39 Updated      

最小环问题

序言

在图论的世界中，环 (Cycle) 是一个基本而核心的概念。它不仅构成了图的复杂拓扑结构，也催生了诸多有趣的算法问题。其中，最小环问题 (Minimum Cycle Problem) 便是极具代表性的一类。顾名思义，该问题旨在寻找图中所有环里，边权之和最小的那一个。

这个问题看似简单，其解法却深刻地联系着图论中一些最经典的算法，如 Floyd-Warshall 和 Dijkstra。对最小环问题的探索，不仅能加深我们对这些基础算法的理解，更能揭示它们在非标准应用场景下的威力与灵活性。它要求我们跳出“模板”的束缚，从算法的动态规划本质或搜索过程中去挖掘解决问题的关键。

本文将系统性地剖析最小环问题的常见变体，包括无向图、有向图、带权图与无权图。我们将从最根本的“拆环为链”思想出发，逐步推导出并实现基于 Floyd-Warshall 和 Dijkstra 的核心解法，并深入探讨其原理、实现细节、复杂度分析以及路径复原等进阶话题。

1. 问题的核心：拆环为链

几乎所有最小环算法的底层逻辑，都源于一个朴素而强大的思想：将环分解为一条链（路径）和一个边。

一个环，无论多么复杂，我们总可以将其视为由一条连接顶点 和 的路径，以及一条连接 和 的边共同构成的闭合结构。如下图所示，环 可以看作是路径 与边 的组合。

这个观察至关重要。它将一个全局的、关于“环”的寻找问题，转化为了一个局部的、关于“路径”和“边”的组合问题。具体来说，一个环的权值可以表示为：

其中 是连接 的路径权值和， 是直接连接它们的边的权值。为了使环的权值最小，我们自然希望构成它的那条路径也是最短的。因此，最小环问题可以被重新表述为：

寻找图中由某条边 及不包含该边的 到 的最短路径所构成的环，并取所有这些环中的最小值。

这个思想为我们提供了求解最小环的通用框架：

  1. 枚举环的某个构成部分（例如，一条边或一个顶点）。
  2. 基于这个枚举的部分，计算出与之配对能形成最小环的另一部分（通常是一条最短路径）。
  3. 在所有可能的组合中，取最小值。

接下来，我们将看到 Floyd-Warshall 和 Dijkstra 算法如何巧妙地实现了这一框架。

2. 无向图的最小环：Floyd-Warshall 的精妙应用

对于一个存在于稠密图（边数 接近 ）或顶点数 不算太大的图，Floyd-Warshall 算法提供了一个极为优雅的 解决方案。

2.1 算法思想

要理解 Floyd-Warshall 如何求解最小环，我们必须首先回顾其作为全源最短路算法的本质。Floyd-Warshall 算法是一个动态规划过程。其核心状态转移方程为：

这个方程的含义是：从顶点 到 的最短路径，可以通过现有的 路径，或者通过先从 到 再从 到 的路径来获得。其外层循环 for k from 1 to n 意味着，在第 轮迭代时，我们尝试引入顶点 作为中转点，来优化任意两点 间的距离。

一个至关重要的性质是：在执行第 轮循环（即 for (int k = 1; k <= n; ++k)）之前，d[i][j] 存储的是从 到 且只允许使用编号在 集合中的顶点作为中间点的最短路径长度。

这个性质正是求解最小环的关键。

考虑一个任意环，它必然存在一个编号最大的顶点，我们称之为 。这个环可以被看作由顶点 、它的两个邻居 和 （这里 ），以及一条连接 和 的、不经过 的路径组成。更进一步，这条连接 和 的路径上的所有中间点，其编号也都必须小于 。

这启发我们：当 Floyd-Warshall 算法的外层循环执行到第 轮时，我们可以尝试寻找以 为最大编号顶点的最小环。

在第 轮循环开始时，对于任意两个顶点 和 (其中 )，d[i][j] 已经记录了它们之间仅使用 作为中转点的最短路径。此时，如果存在边 和 ，它们与路径 就构成了一个以 为“交汇点”的环。该环的长度为：

其中 和 是原始图中边的权值。

因此，我们可以在 Floyd-Warshall 的主循环中，加入寻找最小环的逻辑。算法流程如下：

  1. 初始化邻接矩阵 d[i][j]。若 i 与 j 间有边，d[i][j] 为边权；d[i][i] = 0；其余为无穷大。同时，用一个矩阵 g[i][j] 保存原始图的边权，因为 d[i][j] 会在算法过程中被更新。
  2. 设置全局最小环长度 ans 为无穷大。
  3. 主循环 for k from 1 to n：
    a. 在更新最短路之前，遍历所有满足 1 <= i < k 和 1 <= j < k 的顶点对 。计算 d[i][j] + g[i][k] + g[j][k]，并用这个值更新 ans。
    b. 执行标准 Floyd-Warshall 更新：for i from 1 to n, for j from 1 to n, 更新 d[i][j] = min(d[i][j], d[i][k] + d[k][j])。

关键点：为何更新 ans 的操作必须在更新 d 数组之前？
因为一旦执行了第 轮的 d[i][j] 更新，d[i][j] 的值就可能包含了经过顶点 的路径。此时再用 d[i][j] 计算环长，就违背了“路径 不得经过 ”的前提，可能会导致计算出的路径与边 发生重叠，而不是构成一个简单环。

2.2 实现细节与代码

题意概括: 给定一个 个点 条边的无向带权图，图中可能存在重边和自环，求最小环的权值和。如果图中无环，输出 “No solution.”。

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
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll inf = 1e18;
int n, m;
ll g[255][255]; // 存储原始图的邻接矩阵
ll d[255][255]; // Floyd-Warshall 的 DP 数组
int p[255][255]; // 用于路径复原的前驱节点矩阵
vector<int> path;

void get(int i, int j) {
    if (p[i][j] == 0) return; // 递归基：i, j直接相连
    get(i, p[i][j]);
    path.push_back(p[i][j]);
    get(p[i][j], j);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            g[i][j] = d[i][j] = (i == j ? 0 : inf);
        }
    }

    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        // 处理重边，保留权值最小的边
        g[u][v] = g[v][u] = d[u][v] = d[v][u] = min(g[u][v], w);
    }
    
    ll ans = inf;
    
    for (int k = 1; k <= n; ++k) {
        // 1. 在更新前，寻找以 k 为最大节点的环
        for (int i = 1; i < k; ++i) {
            for (int j = i + 1; j < k; ++j) {
                // d[i][j] 是 i->j 仅用 <k 节点的最短路
                // g[i][k], g[j][k] 是原始边权
                if (d[i][j] != inf && g[i][k] != inf && g[j][k] != inf) {
                    if (ans > d[i][j] + g[i][k] + g[j][k]) {
                        ans = d[i][j] + g[i][k] + g[j][k];
                        // 如果需要输出路径，在这里记录
                        path.clear();
                        path.push_back(k);
                        path.push_back(i);
                        get(i, j);
                        path.push_back(j);
                    }
                }
            }
        }
        
        // 2. 标准 Floyd-Warshall 更新
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (d[i][k] != inf && d[k][j] != inf) {
                    if (d[i][j] > d[i][k] + d[k][j]) {
                        d[i][j] = d[i][k] + d[k][j];
                        p[i][j] = k; // 记录前驱
                    }
                }
            }
        }
    }

    if (ans == inf) {
        cout << "No solution." << endl;
    } else {
        // 输出权值和
        cout << ans << endl; 
        // 如果需要，可以输出路径
        // for(int i=0; i<path.size(); ++i) cout << path[i] << (i == path.size()-1 ? "" : " ");
        // cout << endl;
    }

    return 0;
}

代码解释:

  • g[i][j] 存储原始图的边权，它在算法全程保持不变，用于计算环长。d[i][j] 是动态规划数组，其值会不断被优化。
  • p[i][j] 是用于路径复原的前驱矩阵。当用 d[i][k] + d[k][j] 更新 d[i][j] 时，意味着 的最短路径现在要经过 ，所以我们记录 p[i][j] = k。
  • 外层循环 k 从 1 到 n。
  • 在 k 循环内部，我们首先用两层循环遍历 i < k 和 j < k，检查 d[i][j] + g[i][k] + g[j][k] 是否能构成一个更小的环。这里的 d[i][j] 保证了路径中不含 k 或比 k 更大的节点。
  • 随后，是标准的 Floyd-Warshall 更新过程，用 k 作为中转点去松弛所有点对之间的距离。
  • 复杂度分析:
    • 时间复杂度: 。三重循环是算法的主体，无论是寻找环还是更新最短路，都是 级别。
    • 空间复杂度: 。需要存储 g, d, p 三个邻接矩阵。

2.3 路径复原

找到最小环的权值和通常是第一步，更高阶的要求是输出这个环本身。利用前驱矩阵 p，我们可以做到这一点。

当我们在 k 循环中，通过 ans = d[i][j] + g[i][k] + g[j][k] 找到一个当前最优环时，我们知道这个环由三部分构成：

  1. 顶点
  2. 边 和
  3. 到 的最短路径（仅经过 的节点）

所以，环的顶点序列是 。我们只需要复原 的路径即可。这可以通过一个递归函数 get(i, j) 实现：

  • 路径 i 到 j 的中间点是 p[i][j]。
  • 所以路径分解为 i 到 p[i][j] 和 p[i][j] 到 j 两段。
  • 递归调用 get(i, p[i][j]) 和 get(p[i][j], j)，并在中间输出 p[i][j]。
  • 递归的基准条件是 p[i][j] == 0，表示 是直接相连的，中间没有其他节点。

上述代码中已经包含了路径复原的逻辑。当找到更优的 ans 时，就清空 path 向量，然后按 的顺序将顶点存入。

3. 稀疏图上的对策：Dijkstra 的应用

当图是稀疏图（）时， 的 Floyd-Warshall 算法就显得过于笨重。例如，当 时， 接近 ，无法接受。此时，我们需要一种与边数 关系更密切的算法。

3.1 算法思想

让我们回到“拆环为链”的原始思想。一个环由一条边 和一条不经过该边的 的最短路径构成。这直接催生了一种基于最短路算法的思路：

  1. 枚举图中的每一条边 ，其权值为 。
  2. 对于当前枚举的边 ，我们暂时将其从图中“移除”。
  3. 在移除了边 的新图上，计算从 到 的最短路径，设其长度为 dist(u, v)。
  4. 那么，我们就找到了一个以边 为“接口”的环，其总长度为 dist(u, v) + w(u, v)。
  5. 遍历所有边，将计算出的环长取最小值，即为全局最小环。

对于边权非负的图，计算单源最短路径最有效的算法是 Dijkstra。因此，上述流程可以具体化为：

对图中每一条边 ，都执行一次以 为源点的 Dijkstra 算法，计算出到 的最短距离（在计算中忽略边 本身），从而得到一个候选环。

如何实现“忽略边 ”？有两种常见方式：

  • 物理删除：在每次 Dijkstra 前，临时从邻接表中删除边 和 ，计算完毕后再加回来。这种方式对邻接表的修改较为频繁，实现稍显繁琐且可能效率不高。
  • 逻辑判断：在 Dijkstra 的松弛操作中，当我们从节点 x 准备扩展到其邻居 y 时，增加一个判断。如果当前正在处理的源边是 ，并且 (x, y) 恰好是 (u, v) 或 (v, u)，则跳过这次松弛。这种方式更优雅，无需修改图结构。

3.2 实现细节与代码

题意概括: 同样是给定一个 个点 条边的无向带权图，求最小环。此方法尤其适用于 较大但 相对较小的稀疏图。

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
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, int>;

const ll inf = 1e18;
int n, m;
vector<pair<int, int>> adj[1005]; // 邻接表
vector<tuple<int, int, int>> edges; // 存储所有边

// 在图中计算 s到t 的最短路, 计算时忽略边 (ex, ey)
ll dij(int s, int t, int ex, int ey) {
    vector<ll> d(n + 1, inf);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    d[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [c, u] = pq.top();
        pq.pop();

        if (c > d[u]) continue;
        if (u == t) return d[t]; // 找到 t 的最短路，提前返回

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;

            // 逻辑上"删除"边 (ex, ey)
            if ((u == ex && v == ey) || (u == ey && v == ex)) {
                continue;
            }

            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
    return d[t];
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edges.emplace_back(u, v, w);
    }

    ll ans = inf;

    // 枚举每一条边作为环的一部分
    for (const auto& edge : edges) {
        int u, v, w;
        tie(u, v, w) = edge;
        
        ll res = dij(u, v, u, v);
        
        if (res != inf) {
            ans = min(ans, res + w);
        }
    }

    if (ans == inf) {
        cout << "No solution." << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

代码解释:

  • adj 是邻接表，用于 Dijkstra 算法。
  • edges 向量存储了所有的边信息 。我们需要遍历这个列表来枚举环的“接口边”。
  • 主函数中，我们遍历 edges 里的每一条边 。
  • 对于每条边，我们调用 dij(u, v, u, v)。这个函数计算在不使用边 (u, v) 的情况下，从 u 到 v 的最短路径。
  • dij 函数是标准的 Dijkstra 实现，但在松弛邻居时，加了一句 if ((u == ex && v == ey) || (u == ey && v == ex)) continue; 来实现逻辑上的边删除。
  • 最后，res + w 就是包含边 的一个环的长度，我们用它来更新全局最小环 ans。

复杂度分析:

  • 时间复杂度: 。这里我们使用了优先队列优化的 Dijkstra，其复杂度为 。由于要对 条边都执行一次，所以总时间复杂度是两者的乘积。对于稀疏图，比如 ，复杂度近似为 ，这通常优于 。
  • 空间复杂度: ，主要用于存储邻接表和边列表。

3.3 算法比较与选择

现在我们有了两种解决无向图最小环问题的武器，应该如何选择？

特性 Floyd-Warshall Dijkstra 迭代
核心思想 DP，以顶点为中心 拆环为链，以边为中心
时间复杂度
空间复杂度
适用图类型 稠密图 () 稀疏图 ()
实现难度 相对简单，代码紧凑 稍复杂，需要封装 Dijkstra
负权边 不支持（标准版） 不支持（Dijkstra）

实践指导:

  • 当顶点数 较小（例如 ），无论图的疏密，直接使用 的 Floyd-Warshall 往往是更简单稳妥的选择。代码简短，不易出错。
  • 当顶点数 较大（例如 ），但边数 没那么大时（例如 ）， 会超时，而 级别的复杂度则可能在接受范围内。此时必须使用 Dijkstra 的方法。
  • 这是一个典型的时空权衡和根据数据规模选择算法的例子。深刻理解两种算法的复杂度来源，是做出正确决策的基础。

4. 有向图的最小环：方向性的挑战

当我们从无向图迈向有向图，问题的性质发生了一些微妙而深刻的变化。边的方向性约束了环的构成，一个环必须是 的形式。这意味着我们在无向图中使用的“以 为交汇点连接 ”的Floyd模型不再直接适用，因为边 和 的方向可能是错误的。

幸运的是，我们依然可以沿用“拆环为链”的核心思想，并针对有向图的特性发展出同样优雅的解法。

4.1 Floyd-Warshall 的再审视

对于有向图，Floyd-Warshall 算法的适用性甚至比无向图更直接。考虑任意一个环，它必然可以被拆解为一条从顶点 到 的路径，以及一条从 返回 的边 。

这个环的长度为：

为了找到最小环，我们只需要让 尽可能小，也就是取 到 的最短路径。

这就引出了一个非常简洁的算法：

  1. 首先，运行一次完整的 Floyd-Warshall 算法，计算出图中任意两点 之间的最短路径长度，记为 d[i][j]。
  2. **然后，遍历图中所有的边 **，其权值为 w[j][i]。对于每一条边，计算 d[i][j] + w[j][i]。这代表了由路径 和边 构成的环的长度。
  3. 在所有这些计算出的环长中，取最小值，即为有向图的最小环。

这个方法的正确性是显而易见的。任何一个环都必然包含至少一条边，我们通过枚举这条边 ，并搭配上图中除此边外 到 的最短路径，确保了我们考虑到了所有可能的环，并为每个环找到了其“最短”的表示形式。

与无向图方法的对比:
在无向图的 Floyd-Warshall 解法中，我们必须在第 k 轮更新 d 数组之前计算环长，以保证路径中不含顶点 k。但在有向图中，这个约束消失了。我们先计算出全源最短路，再来组合环。为什么可以这样做？因为最短路 d[i][j] 和边 w[j][i] 不会“意外”地共享顶点而导致路径退化。d[i][j] 本身代表一条从 i 到 j 的简单路径（在无负环的情况下），而边 j->i 只是将头尾连接起来。

4.2 实现细节与代码

题意概括: 给定一个 个点 条边的有向带权图，求最小环的权值和。

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
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll inf = 1e18;
int n, m;
ll w[505][505]; // 存储原始图的边权
ll d[505][505]; // DP数组

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            w[i][j] = d[i][j] = (i == j ? 0 : inf);
        }
    }

    for (int i = 0; i < m; ++i) {
        int u, v;
        ll val;
        cin >> u >> v >> val;
        // 有向图，处理重边
        w[u][v] = d[u][v] = min(w[u][v], val);
    }
    
    // 1. 运行完整的 Floyd-Warshall
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (d[i][k] != inf && d[k][j] != inf) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
    
    ll ans = inf;
    
    // 2. 枚举所有边 (j,i) 与路径 i->j 组合成环
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            // 必须存在 j->i 的边，且 i->j 的路径存在
            if (w[j][i] != inf && d[i][j] != inf) {
                ans = min(ans, d[i][j] + w[j][i]);
            }
        }
    }
    
    if (ans == inf) {
        cout << "No solution." << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

代码解释:

  • w[i][j] 存储原始边权，d[i][j] 用于Floyd-Warshall计算。
  • 代码分为清晰的两部分：首先是标准的全源最短路计算，然后是枚举所有可能的 (路径 i->j) + (边 j->i) 组合来寻找最小环。
  • w[j][i] != inf 确保了边 确实存在，d[i][j] != inf 确保了从 到 是连通的。

复杂度分析:

  • 时间复杂度: 。Floyd-Warshall 算法本身是 ，后续寻找环的过程是 ，总复杂度由前者主导。
  • 空间复杂度: ，用于存储邻接矩阵。

4.3 Dijkstra 的应用：N 次单源最短路

对于稀疏有向图，我们同样可以采用基于 Dijkstra 的策略。这个策略比无向图的“删边法”更为直接和高效。

算法思想:

我们从图中的**每一个顶点 s 出发，运行一次单源最短路算法 (Dijkstra)**。

在以 s 为源点的 Dijkstra 过程中，我们计算 s 到其他所有顶点的最短距离 dist[]。假设在算法的某个时刻，我们正要从顶点 u 松弛其邻居 v，即处理边 u -> v。此时，我们已经有了 s 到 u 的最短路径长度 dist[u]。

如果此时我们发现一条从 u 指回源点 s 的边，即边 u -> s，权值为 w(u, s)，那么我们就发现了一个环：。这个环的长度是 dist[u] + w(u, s)。

这个想法可以推广：在以 s 为源的Dijkstra中，对于任何一条边 u -> v，我们不仅知道 s 到 u 的最短路 dist[u]，我们还能从其他地方（比如邻接矩阵）查到是否存在反向边 v -> s。如果存在，就形成了一个环 ，长度为 dist[u] + w(u, v) + w(v, s)。

一个更简洁的统一思路是：

  1. 对每个顶点 i 从 1 到 n：
    a. 以 i 为源点，运行一次完整的 Dijkstra 算法，计算出 i 到所有其他点的最短路 d[j]。
    b. 在 Dijkstra 运行完毕后，遍历所有入边 (j, i)。对于每条这样的入边，d[j] + w(j, i) 就是一个候选环的长度。
  2. 在所有 n 次 Dijkstra 过程中找到的所有候选环中取最小值。

实际上，我们可以在 Dijkstra 内部完成这个过程：

  1. ans = inf

  2. 对每个顶点 s 从 1 到 n：
    a. 以 s 为源点运行 Dijkstra。
    b. 在 Dijkstra 的主循环中，当我们从优先队列中取出顶点 u 时，遍历 u 的所有出边 u -> v。
    c. 此时，我们已经确定了 s 到 u 的最短路 d[u]。如果存在一条反向边 v -> s，那么 d[u] + w(u, v) + w(v, s) 就是一个环。
    d. 但是这个方法不够普适。一个更简单且完全正确的做法是：在以 s 为源的Dijkstra中，对于从u扩展到v的边(u,v)，如果v恰好是源点s，那么d[u] + w(u,s)就构成了一个环。这个环就是 。

    所以，最终的算法是：
    运行 N 次 Dijkstra。第 i 次以 i 为源点。在这次 Dijkstra 中，对于任意边 u -> v，d[u] + w(u,v) 是一个从 i 出发到 v 的路径长度。用它来更新 d[v]。同时，我们也检查是否存在边 v -> i。如果存在，则 d[v] + w(v,i) 形成一个环，用它来更新全局最小环。

    我们甚至可以简化为：对每个点 s 做一次Dijkstra。对s的每个邻居v，w(s,v)加上v到s的最短路d(v,s)就是一个环。但d(v,s)需要另一次Dijkstra。所以最直接的还是运行N次Dijkstra。

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
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, int>;

const ll inf = 1e18;
int n, m;
vector<pair<int, int>> adj[1005];

ll dij(int s) {
    vector<ll> d(n + 1, inf);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    ll min_cyc = inf;

    d[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [c, u] = pq.top();
        pq.pop();

        if (c > d[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;

            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
            // 关键点：如果v就是起点，则s->...->u->s形成环
            if (v == s) {
                min_cyc = min(min_cyc, d[u] + w);
            }
        }
    }
    return min_cyc;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    ll ans = inf;
    for (int i = 1; i <= n; ++i) {
        // 以每个点为源点，寻找经过该点的最小环
        ans = min(ans, dij(i));
    }

    if (ans == inf) {
        cout << "No solution." << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

代码解释:
这段代码存在一个微妙的陷阱。在标准Dijkstra中，一旦一个点的最短路确定（从优先队列中弹出），就不会再更新它。但为了找到环，我们可能需要一条非最短的 s->...->u 路径。例如，最短路 s->u 可能与后续的 u->s 边有重合，而次短路则不会。

一个更稳健的Dijkstra变体是**不使用 if (c > d[u]) continue;**，或者说，允许一个节点被多次更新并入队。这实际上将Dijkstra退化为了一个类似SPFA的宽度优先搜索，但它能保证找到所有路径。然而，这会牺牲效率。

正确的、高效的Dijkstra做法是：对每个点 s，运行一次标准的Dijkstra。Dijkstra计算出的是从 s 出发的最短路树。一个环由一条树边或前向边，以及一条非树边（横叉边或后向边）组成。
当松弛边 u -> v 时：

  • 如果 v 未访问，正常松弛。
  • 如果 v 已访问，则 u -> v 是一条非树边。此时，路径 构成一个环。但 的路径未知。
  • 最简单的方法还是我们之前的 Floyd 思想的 Dijkstra 版本：对于每一条边 u -> v，在移除了这条边的图上跑一次从 v 到 u 的Dijkstra。总复杂度为 。

所以，对于有向图，最直接的稀疏图解法是：

  1. ans = inf
  2. 对于图中每条边 u -> v，权值为 w：
    a. 计算在不含边 (u,v) 的情况下，从 v 到 u 的最短路 d(v,u)。
    b. ans = min(ans, d(v,u) + w)。
    这个逻辑和无向图完全一样，只是 Dijkstra 只需要从 v 跑，而不是双向。

5. 负权边与最小环

引入负权边会使问题变得复杂。Dijkstra算法不再适用，我们必须求助于能处理负权的算法，如Bellman-Ford、SPFA，或者更高级的Johnson算法。

5.1 基于SPFA/Bellman-Ford的解法

如果图中存在负权边但没有负权环，我们可以用SPFA或Bellman-Ford替换Dijkstra。

  • 稠密图: Floyd-Warshall 天然支持负权边（只要无负环），其有向图解法 min(d[i][j] + w[j][i]) 依然有效。如果 d[i][i] 在算法结束后小于0，说明存在负环，最小环问题无解（可以无限小）。
  • 稀疏图: 我们可以用SPFA替换Dijkstra，执行 次单源最短路。即，对每个点 s，以 s 为源跑SPFA，在过程中寻找指向 s 的边来闭合环。或者，更稳妥地，对每条边 u -> v，用SPFA计算 v 到 u 的最短路。复杂度在最坏情况下会退化到 ，总复杂度为 ，通常不可接受。

5.2 Johnson算法：终极解决方案

当图中既有负权边，又需要高效求解（优于 ），Johnson算法登场了。它是一种巧妙地将图转化为无负权边图，从而可以使用Dijkstra的方法。

Johnson算法核心思想:

  1. 引入新源点: 添加一个新顶点 ，并从 向所有其他顶点 添加一条权值为0的边 。
  2. 计算势能 (Potential): 以 为源点，运行一次SPFA或Bellman-Ford，计算出 到所有顶点 的最短距离 。如果在此过程中检测到负权环，则原图的最小环（如果要求简单环）问题可能变得非常复杂或无解（非简单环），算法终止。这个 就作为每个顶点的“势”。
  3. 重设边权 (Re-weighting): 对原图中的每一条边 ，其权值为 ，更新其权值为 。
  4. 关键性质:
    • 非负性: 新的边权 一定是非负的。因为根据三角不等式，h(v) <= h(u) + w(u, v)，所以 w(u, v) + h(u) - h(v) >= 0。
    • 环权不变性: 对于任何一个环 ，其在新图中的权值和 与原图中的权值和 相等。
  5. 求解: 现在我们有了一个边权非负的新图，且环权与原图完全相同。我们可以在这个新图上放心地使用 次Dijkstra来求解最小环了。

题意概括: 给定一个可能包含负权边的有向图，求其最小环。如果存在负环，也需考虑。

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
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, int>;

const ll inf = 1e18;
int n, m;
vector<tuple<int, int, int>> edges;
vector<pair<int, int>> adj[1005];
ll h[1005];

// SPFA计算势能h，并检测负环
bool spfa() {
    vector<int> cnt(n + 1, 0);
    vector<bool> inq(n + 1, false);
    queue<int> q;

    for (int i = 1; i <= n; ++i) {
        h[i] = 0; // 对应s0到各点距离为0
        q.push(i);
        inq[i] = true;
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;

        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (h[v] > h[u] + w) {
                h[v] = h[u] + w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                    cnt[v]++;
                    if (cnt[v] > n) return false; // 发现负环
                }
            }
        }
    }
    return true;
}

// 在重赋权图上跑Dijkstra
ll dij(int s, const vector<vector<pair<int, ll>>>& new_adj) {
    vector<ll> d(n + 1, inf);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    ll min_cyc = inf;
    
    d[s] = 0;
    pq.push({0, s});
    
    while(!pq.empty()){
        auto [c, u] = pq.top();
        pq.pop();
        
        if(c > d[u]) continue;
        
        for(auto& edge : new_adj[u]){
            int v = edge.first;
            ll w = edge.second;
            
            // 找到了一个环 s -> ... -> u -> v
            // 原始权重是 d[v] - h[s] + h[v]
            // 但是d[u] + w 已经是重赋权后的路径长
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }

    // 遍历所有到达s的边j->s，计算环长
    for(int j=1; j<=n; ++j){
        for(auto& edge : new_adj[j]){
            if(edge.first == s){
                if(d[j] != inf){
                    min_cyc = min(min_cyc, d[j] + edge.second);
                }
            }
        }
    }
    return min_cyc;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        edges.emplace_back(u, v, w);
    }
    
    // 1. SPFA计算势能
    if (!spfa()) {
        // 如果原图就有负环，那么最小环问题可能无定义（非简单环）
        // 具体取决于题目定义，这里假设我们只关心简单环
        // 或者题目保证无负环
    }

    // 2. 重赋权
    vector<vector<pair<int, ll>>> new_adj(n + 1);
    for (const auto& edge : edges) {
        int u, v, w;
        tie(u, v, w) = edge;
        new_adj[u].push_back({v, (ll)w + h[u] - h[v]});
    }

    // 3. 对每个点跑Dijkstra
    ll ans = inf;
    for (int i = 1; i <= n; ++i) {
        ll res = dij(i, new_adj);
        if(res != inf){
            // 环权不变，直接使用重赋权后的环长
           ans = min(ans, res);
        }
    }

    if (ans == inf) {
        cout << "No solution." << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

代码解释:

  • spfa() 函数模拟了添加超级源点 的过程。将所有点的 h 初始化为0，等价于 到所有点距离为0，然后进行松弛。它计算了势能 h[]。
  • 主函数中，先调用 spfa。
  • 然后，根据 w'(u,v) = w(u,v) + h(u) - h(v) 构建一个新的邻接表 new_adj。
  • 最后，在 new_adj 上对每个点 i 运行一次 dij。在 dij 内部，我们找到的环长 d[j] + w'(j,i) 就是最终的环长，因为环权不变。
  • 复杂度分析:
    • SPFA: 最坏 ，一般情况下远快于此。
    • 次 Dijkstra: 。
    • 总复杂度: 。这是解决带负权稀疏图最小环问题的标准高效解法。

6. 特殊环问题与思想拓展

除了标准的最小权值环，还存在一些有趣的变体，它们的解法进一步拓展了我们对图算法的理解。

6.1 0-1图的最小环（Girth）

在一个无权图（或所有边权为1的图）中，最小环问题被称为寻找图的**围长 (Girth)**。

算法思想:

由于边权为1，最短路算法退化为广度优先搜索 (BFS)。我们可以借鉴Dijkstra迭代法的思想：枚举每一条边 ，暂时删除它，然后从 开始BFS寻找一条到 的最短路。

  1. ans = infinity
  2. 对于图中每一条边 :
    a. 从图中逻辑上移除边 。
    b. 以 为源点，执行BFS，计算到 的最短距离 dist(v)。
    c. 如果 可达，则发现一个环，长度为 dist(v) + 1。用此更新 ans。
    d. 逻辑上恢复边 。

代码实现:

题意概括: 给定一个 个点 条边的无向无权图，求其最小环的长度。

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
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 1e9;
int n, m;
vector<int> adj[1005];
vector<pair<int, int>> edges;

// BFS求s到t的最短路, 忽略边(ex,ey)
int bfs(int s, int t, int ex, int ey) {
    vector<int> d(n + 1, -1);
    queue<int> q;

    d[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == t) return d[t];

        for (int v : adj[u]) {
            if ((u == ex && v == ey) || (u == ey && v == ex)) continue;
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges.push_back({u, v});
    }

    int ans = inf;
    for (auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        int res = bfs(u, v, u, v);
        if (res != -1) {
            ans = min(ans, res + 1);
        }
    }
    
    if (ans == inf) {
        cout << "No solution." << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

复杂度分析:

  • 时间复杂度: 。对 条边，每条边都执行一次 的BFS。
  • 空间复杂度: 。

另一种思路: 运行 次BFS。以每个点 i 为源进行BFS。在BFS过程中，若从 u 扩展到 v 时发现 v 已被访问过，且 v 不是 u 的父节点，则发现一个环。环长为 d[u] + d[v] + 1。总复杂度为 ，在稀疏图上可能差于前者。

6.2 最小均值环 (Minimum Mean Cycle)

这是一个更高级的问题：寻找一个环 ，使得其平均权值最小化。即最小化：

算法思想：二分答案 + 负环判定

这个问题是二分答案的经典应用场景。假设我们猜测最小均值是 。我们想判断是否存在一个环 使得其均值小于等于 。

这个不等式是关键。它告诉我们，判断是否存在均值小于等于 的环，等价于：将图中每条边的权值 修改为 ，然后判断新图中是否存在权值和非正的环。
如果存在一个负环，那么一定存在一个均值小于 的环。如果只存在0环，说明存在均值等于 的环。

于是，算法流程浮出水面：

  1. 确定答案的上界 R 和下界 L (例如，图中边权的最小/最大值)。
  2. 进行二分查找。每次取 mid = (L+R)/2。
  3. 构建一个新图，边权为 w(e) - mid。
  4. 使用SPFA或Bellman-Ford在此新图上检测是否存在负环。
    • 若存在负环，说明存在均值更小的环，所以真正的答案在 [L, mid] 区间。令 R = mid。
    • 若不存在负环，说明所有环的均值都大于 mid。真正的答案在 [mid, R] 区间。令 L = mid。
  5. 重复二分，直到 R-L 小于一个足够小的精度 eps。

代码实现:

题意概括: 给定一个有向带权图，找出权值平均数最小的环。

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
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const double eps = 1e-9;
int n, m;
vector<tuple<int, int, int>> edges;
double d[5005]; // 距离数组，用double

// 检查是否存在负环
bool check(double x) {
    for (int i = 1; i <= n; ++i) d[i] = 0;
    
    // Bellman-Ford
    for (int i = 0; i < n; ++i) { // n轮松弛
        bool relaxed = false;
        for (const auto& edge : edges) {
            int u, v, w;
            tie(u, v, w) = edge;
            if (d[v] > d[u] + w - x) {
                d[v] = d[u] + w - x;
                relaxed = true;
            }
        }
        if (!relaxed) return false; // 没有更新，无负环
        if (i == n - 1 && relaxed) return true; // 第n轮仍能松弛，有负环
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    double l = 1e9, r = -1e9;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.emplace_back(u, v, w);
        l = min(l, (double)w);
        r = max(r, (double)w);
    }
    
    while (r - l > eps) {
        double mid = l + (r - l) / 2;
        if (check(mid)) {
            r = mid; // 存在均值<=mid的环，尝试更小的
        } else {
            l = mid; // 不存在，答案肯定比mid大
        }
    }
    
    cout << fixed << setprecision(8) << l << endl;

    return 0;
}

复杂度分析:

  • check 函数 (Bellman-Ford): 。
  • 二分次数: ，其中 是权值范围。
  • 总复杂度: 。

7. 写在最后

我们从“拆环为链”这一简单而深刻的洞察出发，系统地走过了从无向图到有向图，从非负权到负权，从稠密图到稀疏图的最小环求解之旅。

  • 对于无向图，我们掌握了基于Floyd-Warshall的 精妙解法，以及基于Dijkstra迭代的 稀疏图方案。
  • 对于有向图，我们发现Floyd-Warshall的应用更为直接，而 次Dijkstra则构成了稀疏图的基础解法。
  • 面对负权边，Johnson算法通过“势能”与“重赋权”的优雅变换，将问题转化为我们熟悉的非负权场景，展现了算法组合的力量。
  • 我们还探索了Girth和最小均值环等变体，前者将问题简化为BFS的应用，后者则引入了二分答案与负环判定的强大思想范式。

最小环问题是图论算法的一个绝佳的交汇点。它不仅仅是模板的套用，更考验我们对算法本质的理解——Floyd-Warshall的动态规划过程，Dijkstra的搜索边界，SPFA的松弛原理，以及问题转化的智慧。在解决实际问题时，准确分析图的性质（有向/无向、稠密/稀疏、带权/无权、正权/负权），并选择与之匹配的最高效算法，是通往成功的关键。

附录：例题选讲

洛谷P6175 无向图的最小环问题

题目描述

给定一张无向图，求图中一个至少包含 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 No solution.。

输入格式

第一行两个正整数 表示点数和边数。

接下来 行，每行三个正整数 ，表示节点 之间有一条长度为 的边。

输出格式

输出边权和最小的环的边权和。若无解，输出 No solution.。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

输出 #1

1
61

说明/提示

样例解释：一种可行的方案：。

对于 的数据，。

对于 的数据，。

对于 的数据，，，。

无解输出包括句号。

思路分析

这是一道经典的无向图最小环模板题。我们首先分析数据范围：。这个顶点数量级是一个非常强烈的信号，暗示着一个复杂度为 的算法是可以通过的，因为 ，完全在可接受的时间范围内。

这让我们立即想到了本文第2节中讨论的，基于 Floyd-Warshall 算法的解决方案。该方法优雅且代码实现相对简洁，非常适合此类 较小的场景。

我们再次回顾其核心思想：

  1. 一个环可以看作是由一条路径和一条边构成的。更具体地，一个以编号最大的顶点 构成的环，可以分解为一条从 到 的路径（其中 ，且路径上的中间点也都小于 ），以及边 和 。
  2. Floyd-Warshall 算法的动态规划过程天然地提供了这一结构。在算法的外层循环进行到第 k 轮之前，d[i][j] 存储的正是从 到 且只允许使用编号小于 的顶点作为中转的最短路径。
  3. 因此，我们可以在第 k 轮循环更新最短路之前，遍历所有满足 i < k 和 j < k 的点对 ，尝试用 d[i][j] + g[i][k] + g[j][k] 来更新最小环的答案。其中 g[][] 存储原始图的边权，因为 d[][] 的值会被修改。

代码实现

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
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll inf = 1e12; // 权值和可能较大，inf要开够
int n, m;
ll g[105][105]; // 存储原始图的邻接矩阵
ll d[105][105]; // Floyd-Warshall的DP数组

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            g[i][j] = d[i][j] = (i == j ? 0 : inf);
        }
    }

    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        // 处理重边，保留权值最小的边
        if (w < g[u][v]) {
            g[u][v] = g[v][u] = d[u][v] = d[v][u] = w;
        }
    }
    
    ll ans = inf;
    
    for (int k = 1; k <= n; ++k) {
        // 在更新前，寻找以k为最大节点的环
        for (int i = 1; i < k; ++i) {
            for (int j = i + 1; j < k; ++j) {
                // d[i][j]是i->j仅用<k节点的最短路
                // g[i][k]和g[k][j]是原始边权
                if (d[i][j] != inf && g[i][k] != inf && g[k][j] != inf) {
                    ans = min(ans, d[i][j] + g[i][k] + g[k][j]);
                }
            }
        }
        
        // 标准Floyd-Warshall更新
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (d[i][k] != inf && d[k][j] != inf) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }

    if (ans == inf) {
        cout << "No solution." << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}
  • 复杂度分析: 时间复杂度 ，空间复杂度 。对于本题数据范围，该解法是高效且正确的。

P10044 [CCPC 2023 北京市赛] 最小环

题目描述

小 I 发明了 的有向图最小环，于是他想考考你。

给定一个 个节点、 条边的有向图，每条边有正整数边权。你需要求出图上的一个环使得环上边的边权和最小。求出这个最小值，或者报告不存在环。

当然，由于你不会 的有向图最小环，于是小 I 放宽了条件：保证输入的图是弱连通的，且 不会很大。一个图是弱连通的当且仅当将有向边换为无向边后图连通。

输入格式

第一行两个整数 ，表示图的点数和边数。

接下来 行每行三个整数 ，表示一条从 到 、边权为 的有向边。保证图是弱连通的。

输出格式

如果图中不存在环，输出 -1，否则输出一个整数表示最小环的长度和。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
4 6
1 2 1
4 3 3
4 1 9
2 4 1
3 1 2
3 2 6

输出 #1

1
7

输入输出样例 #2

输入 #2

1
1 0

输出 #2

1
-1

输入输出样例 #3

输入 #3

1
2
1 1
1 1 1

输出 #3

1
1

说明/提示

【样例解释 1】

最小环为 。

【样例解释 3】

最小环为 。

思路分析

本做法通过一个多阶段的流程来解决稀疏图的最小环问题。首先，应用 Tarjan 算法将图分解为多个强连通分量 (SCC)，其依据是任何简单环都完全包含在单个 SCC 内，这使得问题可以被分解到每个 SCC 中独立处理。在处理单个 SCC 时，通过一次深度优先搜索（DFS）建立一棵生成树，从而将 SCC 内的边分为树边和非树边。非树边的端点在后续计算中扮演重要角色。接着，通过第二次 DFS 遍历，该算法计算两类信息：一是各节点相对于 DFS 树根的路径距离，此距离将用作后续计算的势；二是对所有非树边的端点，依据 DFS 序进行线性化，并确定每个节点在 DFS 树中对应子树所覆盖的线性区间。算法的核心部分是为每条非树边 (v, u) 执行一次修改版的 Dijkstra 算法，以计算从 u 到 v 的最短路径。在此 Dijkstra 算法中，一个线段树结构取代了标准的优先队列，用于维护各非树边端点经“势”调整后的距离。其主要优化在于，当松弛操作沿树边从节点 k 向其子树进行时，原本需要对子树内多个节点进行的单点更新，被转化为对线段树上代表 k 子树的单个区间的批量更新。通过在每个 SCC 中对所有非树边应用这一线段树优化的 Dijkstra 过程，最终确定全局的最小环。

参考代码

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
149
150
151
152
153
154
155
156
157
158
159
160
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, int>;

const int N = 3e5 + 5;
const ll inf = 1e16;

int n, m;
vector<pii> e[N], e2[N], e3[N];
int dfn[N], low[N], st[N], col[N], tp, tot, gn;
bool vis[N], bj[N];
ll lw[N], fd[N], ans = inf;
int ld[N], rd[N];

struct node {
    pii ma, mb;
    ll tg;
} tr[N << 2];

void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    st[++tp] = u; vis[u] = true;
    for (auto& edge : e[u]) {
        int v = edge.first;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        int c = u; gn++;
        while (true) {
            vis[st[tp]] = false;
            col[st[tp]] = c;
            if (st[tp--] == u) break;
        }
    }
}

void dfs1(int u, int c) {
    vis[u] = true;
    for (auto& edge : e[u]) {
        int v = edge.first, w = edge.second;
        if (col[v] != c) continue;
        if (!vis[v]) {
            e2[u].push_back({v, w});
            dfs1(v, c);
        } else {
            e3[u].push_back({v, w});
            bj[u] = bj[v] = true;
        }
    }
}

void dfs2(int u) {
    if (bj[u]) ld[u] = ++tp, st[tp] = u;
    for (auto& edge : e2[u]) {
        int v = edge.first, w = edge.second;
        lw[v] = lw[u] + w;
        dfs2(v);
    }
    if (bj[u]) rd[u] = tp;
}

void psu(int p) {
    tr[p].mb = min(tr[p << 1].mb, tr[p << 1 | 1].mb);
    pii val = {tr[p].mb.first + tr[p].tg, tr[p].mb.second};
    tr[p].ma = min({tr[p << 1].ma, tr[p << 1 | 1].ma, val});
}

void build(int p, int l, int r) {
    tr[p].tg = inf;
    if (l == r) {
        int u = st[l];
        tr[p].ma = {inf, u};
        tr[p].mb = {lw[u], u};
        return;
    }
    int mid = (l + r) / 2;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
    psu(p);
}

void mdf(int p, int l, int r, int ql, int qr, ll w) {
    if (tr[p].mb.first == inf) return;
    if (l >= ql && r <= qr) {
        if (w < tr[p].tg) {
            tr[p].tg = w;
            pii val = {tr[p].mb.first + tr[p].tg, tr[p].mb.second};
            tr[p].ma = min(tr[p].ma, val);
        }
        return;
    }
    int mid = (l + r) / 2;
    if (ql <= mid) mdf(p << 1, l, mid, ql, qr, w);
    if (qr > mid) mdf(p << 1 | 1, mid + 1, r, ql, qr, w);
    psu(p);
}

void ban(int p, int l, int r, int k) {
    if (l == r) { tr[p].tg = tr[p].ma.first = tr[p].mb.first = inf; return; }
    int mid = (l + r) / 2;
    if (k <= mid) ban(p << 1, l, mid, k);
    else ban(p << 1 | 1, mid + 1, r, k);
    psu(p);
}

void run_dij(int t, int s, int w0) {
    for (int i = 1; i <= tp; ++i) fd[st[i]] = inf;
    build(1, 1, tp);
    mdf(1, 1, tp, ld[s], ld[s], (ll)w0 - lw[s]);

    while (true) {
        int u = tr[1].ma.second;
        fd[u] = tr[1].ma.first;
        if (u == t || fd[u] >= inf) break;
        ban(1, 1, tp, ld[u]);
        mdf(1, 1, tp, ld[u], rd[u], fd[u] - lw[u]);
        for (auto& edge : e3[u]) {
            int v = edge.first; ll w = edge.second;
            if (bj[v] && fd[v] == inf) {
                mdf(1, 1, tp, ld[v], ld[v], fd[u] + w - lw[v]);
            }
        }
    }
    if (fd[t] != inf) ans = min(ans, fd[t]);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        e[u].push_back({v, w});
    }

    for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i);
    
    for (int i = 1; i <= n; ++i) { 
        if (col[i] != i || vis[i]) continue;
        dfs1(i, i);
        tp = 0; dfs2(i);
        if(tp == 0) continue;

        for (int j = 1; j <= tp; ++j) {
            int u = st[j];
            for (auto& edge : e3[u]) {
                int v = edge.first, w = edge.second;
                run_dij(u, v, w);
            }
        }
    }
    
    cout << (ans >= inf ? -1 : ans) << endl;
    return 0;
}
  • Title: 最小环
  • Author: YZY
  • Created at : 2025-06-16 23:53:39
  • Updated at : 2025-06-16 23:53:39
  • Link: https://blog.dtoj.team/2025/06/16/最小环/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
最小环
  1. 最小环问题
  2. 序言
  3. 1. 问题的核心：拆环为链
  4. 2. 无向图的最小环：Floyd-Warshall 的精妙应用
    1. 2.1 算法思想
    2. 2.2 实现细节与代码
    3. 2.3 路径复原
  • 3. 稀疏图上的对策：Dijkstra 的应用
    1. 3.1 算法思想
    2. 3.2 实现细节与代码
    3. 3.3 算法比较与选择
  • 4. 有向图的最小环：方向性的挑战
    1. 4.1 Floyd-Warshall 的再审视
    2. 4.2 实现细节与代码
    3. 4.3 Dijkstra 的应用：N 次单源最短路
  • 5. 负权边与最小环
    1. 5.1 基于SPFA/Bellman-Ford的解法
    2. 5.2 Johnson算法：终极解决方案
  • 6. 特殊环问题与思想拓展
    1. 6.1 0-1图的最小环（Girth）
    2. 6.2 最小均值环 (Minimum Mean Cycle)
  • 7. 写在最后
  • 附录：例题选讲
  • 洛谷P6175 无向图的最小环问题
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 输入输出样例 #1
    5. 输入 #1
    6. 输出 #1
    7. 说明/提示
    8. 思路分析
    9. 代码实现
  • P10044 [CCPC 2023 北京市赛] 最小环
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 输入输出样例 #1
    5. 输入 #1
    6. 输出 #1
    7. 输入输出样例 #2
    8. 输入 #2
    9. 输出 #2
    10. 输入输出样例 #3
    11. 输入 #3
    12. 输出 #3
    13. 说明/提示
    14. 思路分析
    15. 参考代码