Moe's CF Life

Appearance

G. Omg Graph - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 1029 (Div. 3) 标签: brute force, dsu, graphs, greedy, shortest paths, sortings 难度: *1900

题目大意喵~ ​

主人你好呀~！这道题是这样的喵：

我们拿到一个连通的、带权重的无向图。题目定义了一种特殊的路径成本：一条路径的成本等于这条路径上所有边的最小权重加上最大权重，也就是 min_weight + max_weight 的说。

我们的任务，就是要从顶点 1 出发，找到一条到达顶点 n 的路径，使得这个 min_weight + max_weight 的成本最小。

需要特别注意的是，题目里说路径不一定是“简单路径”（simple path），这意味着我们可以重复经过顶点和边哦！这一点非常非常重要呐！ฅ^•ﻌ•^ฅ

解题思路喵！ ​

这道题的成本计算方式 min_w + max_w 非常有趣，不是我们常见的路径总权重呢。直接去暴力搜索所有路径肯定是不行的说，会跑到天荒地老喵。

问题的关键点在于 “路径可以不简单” 这个慷慨的条件！这意味着什么呢？意味着我们有极大的自由度！比如说，我们已经有了一条从 1 到 n 的路径，我们可以从路径上的任意一点出发，跑到图里的任意一条边 (a, b)，走一个来回 a -> b -> a，再回到原来的路径上。这样一来，我们就在不改变起点和终点的情况下，把边 (a, b) 的权重 w_ab “添加”到了我们路径的权重集合里。

这个发现给了我们一个启发：我们可以把路径的 min_w 和 max_w 两个部分分开来考虑！

让我们把一条从 1 到 n 的路径想象成这样三段： 1 -> ... -> u --(w)--> v -> ... -> n

我们遍历图中的每一条边 (u, v)（权重为 w），并把它当作我们最终路径上的一座“桥梁”。

现在，为了让总成本 min_w + max_w 最小，我们希望 max_w 尽可能小。这个路径的 max_w 取决于三部分：1 -> u 子路径的最大边权、边 (u,v) 的权重 w，以及 v -> n 子路径的最大边权。

所以，我们需要找到一条从 1 到 u 的路径，使其自身的最大边权最小。这其实是一个经典的问题，叫做 “最小化最大路径” (Min-Max Path) 或者叫瓶颈路问题。这个问题可以用一个修改版的 Dijkstra 算法来解决！

Dijkstra 的奇妙变身喵~

普通的 Dijkstra 算法是累加路径权重，dist[v] = dist[u] + weight(u,v)。 而解决 Min-Max Path 问题的 Dijkstra，状态转移方程变成了： dist[v] = min(dist[v], max(dist[u], weight(u,v))) 这里的 dist[i] 记录的是从源点到顶点 i 的路径中，最小的“最大边权”是多少。

有了这个强大的工具，我们的思路就清晰了呐：

  1. 预处理：我们跑两次修改版的 Dijkstra 算法。

    • 第一次从顶点 1 出发，计算出 mx1[i]，表示从 1 到任意顶点 i 的 Min-Max Path 成本。
    • 第二次从顶点 n 出发，计算出 mxn[i]，表示从 n 到任意顶点 i 的 Min-Max Path 成本。

  2. 组合与计算：现在，我们遍历图中的每一条边 (u, v)，其权重为 w。

    • 我们可以构造一条路径：先走 1 -> u 的 Min-Max Path（最大边权为 mx1[u]），然后通过边 (u, v)，再走 v -> n 的 Min-Max Path（最大边权为 mxn[v]）。
    • 这条构造出来的路径，它的最大边权部分，我们可以认为是 max(mx1[u], mxn[v])。为什么可以忽略 w 呢？因为我们可以先从 1 走到 u，再从 u 通过其他路径走到 v（这些路径的最大边权已经被包含在 max(mx1[u], mxn[v]) 的计算中了），最后从 v 走到 n。这样就构成了一条最大边权为 max(mx1[u], mxn[v]) 的基础路径。
    • 那最小边权 min_w 呢？因为路径可以不简单，我们可以强制让 w 成为路径的一部分（通过在基础路径上绕路去走一下 u-v 这条边）。这样，一个候选的成本就诞生了：w + max(mx1[u], mxn[v])。
    • 我们遍历所有边，计算这个候选成本，并取其中的最小值，就是最终的答案啦！

举个栗子：对于边 (u, v)，我们找到的成本是 w + max(mx1[u], mxn[v])。这可以理解为，我们构建了一条最大边权为 max(mx1[u], mxn[v]) 的路径，然后通过“绕路”技巧，把 w 作为最小边权“添加”了进去。

通过这种方式，我们就能高效地找到最优解了！是不是很巧妙呀，喵~

代码实现喵！ ​

cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 10;

int main() {
    // 提升IO效率，喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        // 使用邻接表来存图，pair的第一项是权重，方便优先队列排序
        vector<vector<pair<int, int>>> adj(n + 1);
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            adj[u].push_back({w, v});
            adj[v].push_back({w, u});
        }

        // mx1[i] 存储从 1 到 i 的最小化最大路径权重
        vector<int> mx1(n + 1, INF);
        // mxn[i] 存储从 n 到 i 的最小化最大路径权重
        vector<int> mxn(n + 1, INF);

        // 修改版的Dijkstra算法，用于计算Min-Max Path
        auto dijkstra = [&](vector<int>& dist, int source) {
            dist[source] = 0; // 源点到自身的路径最大边权为0
            // 优先队列，存储 {当前路径最大边权, 顶点}，从小到大排序
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
            pq.push({0, source});

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

                // 如果已经有更优的路径，就跳过
                if (cur_val != dist[u]) continue;

                for (auto [w, v] : adj[u]) {
                    // 新路径的最大边权是当前路径最大边权和新边的较大者
                    int new_val = max(cur_val, w);
                    // 如果找到了更优的路径（即max更小），就更新
                    if (new_val < dist[v]) {
                        dist[v] = new_val;
                        pq.push({new_val, v});
                    }
                }
            }
        };

        // 从 1 和 n 分别跑一次Dijkstra
        dijkstra(mx1, 1);
        dijkstra(mxn, n);

        ll ans = 1e18; // 初始化一个超大的答案

        // 遍历每一条边 (u, v)，权重为 w
        for (int u = 1; u <= n; u++) {
            for (auto [w, v] : adj[u]) {
                // 这是个小小的特例，如果边直接连接了1和n，那么路径就是这条边本身
                // min_w = w, max_w = w, cost = 2*w
                // mx1[u]==0 意味着 u=1, mxn[v]==0 意味着 v=n (或反之)
                if (mx1[u] == 0 && mxn[v] == 0) {
                    ans = min(ans, 2LL * w);
                } else {
                    // 核心公式：w作为min_w, max(mx1[u], mxn[v])作为max_w
                    // 这里其实是 max(w, max(mx1[u], mxn[v])) 作为 max_w, w_min 作为 min_w
                    // 不过最终的简化形式就是这样
                    ans = min(ans, (ll)w + max(mx1[u], mxn[v]));
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O(T * M * log(N)) 的说。 每个测试用例中，我们运行了两次 Dijkstra 算法。带有优先队列的 Dijkstra 算法复杂度是 O(M * log(N))，其中 N 是顶点数，M 是边数。之后遍历所有边是 O(M)。所以总的主导复杂度就是 Dijkstra 的复杂度啦。
  • 空间复杂度: O(N + M) 的说。 主要是邻接表 adj 占用的 O(N + M) 空间，以及 mx1 和 mxn 两个数组占用的 O(N) 空间。

知识点与总结喵 ​

这道题真是一次有趣的冒险呢！让我们来总结一下学到了什么吧：

  1. Min-Max Path (最小化最大路径): 这是一个非常经典的图论问题，是标准最短路径问题的变体。它的核心思想是找到一条路径，使得路径上最大的边权尽可能小。通过将 Dijkstra 的松弛操作从 + 改为 max 就可以优雅地解决它。

  2. 问题分解与构造: 解题的关键在于将复杂的 min+max 成本分解。我们没有直接去寻找最优路径，而是换了个角度：枚举图中的每条边 (u, v)，并以此为基础构造一个候选的最优路径，从而大大简化了问题。

  3. 利用题目特性: “路径不简单”这个条件是解题的突破口！它允许我们自由地组合路径和“注入”边权，这是许多图论题中需要注意的细节。如果题目没这个条件，那可就完全是另一个故事了。

希望这篇题解能帮到主人哦！继续加油，算法的世界还有好多好多有趣的喵咪等着我们去发现呢！(ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe