D. Eternal Victory - 题解

比赛与标签

比赛: Codeforces Beta Round 57 (Div. 2) 标签: dfs and similar, graphs, greedy, shortest paths, trees 难度: *1800

喵~ 题目大意是什么呀？

主人 sama，欢迎来到我的题解小屋~ 这道题目是关于一个叫做 Shapur 的人，他想去遍访波斯的所有 n 个城市，喵！

这些城市和连接它们的道路构成了一棵树（也就是任意两个城市之间都只有一条唯一的路径）。Shapur 从城市 1 出发，需要访问所有城市至少一次。他可以自由选择在任何一个城市结束他的旅程。我们的任务就是帮助他找到一条总路程最短的路线，并告诉他这个最短路程是多少，的说。

简单来说就是：

• 输入: 一个 n 个点 n-1 条边的带权无向图（一棵树）。
• 任务: 从节点 1 出发，遍历所有节点，求最小的总路径长度。
• 输出: 一个整数，表示最小的总路径长度。

解题思路大揭秘！

嘿嘿，这个问题看起来有点复杂，但只要我们换个角度思考，就会变得非常简单哦，喵~

首先，我们来想一个最“笨”的办法。如果要确保访问到每一个城市，一个万无一失的策略就是：从起点出发，每走到一条路的尽头，如果那边还有没去过的分支，就继续探索；如果一个分支都探索完了，就原路返回，去探索别的分支。这种走法，就像一次完整的深度优先搜索（DFS）遍历。

在这种“走遍所有路再回来”的策略下，每一条道路都会被恰好走两次——一次“去”，一次“回”。那么总路程就是所有道路长度之和再乘以 2。对吧？

但是！题目给了我们一个天大的好消息：我们不必回到起点城市 1，可以在任何城市结束旅程！这正是我们优化的关键所在，呐！

*（小猫画的示意图，喵~）*

想象一下，我们最终的旅程是从城市 1 开始，到某个城市 k 结束。这条从 1 到 k 的路径，我们只需要走一遍，就不用再回头了！而所有不在 1 -> k 主路径上的分支小路，我们仍然需要“去”了再“回”，所以那些路还是得走两遍。

所以，相比于“所有路都走两遍”的总路程，我们现在可以“省下”一段路程，这段路程正好就是从起点 1 到我们选定的终点 k 的那条路径的长度。

为了让总路程最小，我们当然希望“省下”的路程最长！

所以，我们的策略就变得非常清晰了，喵~

1. 计算总成本: 先假设所有道路都需要走两遍，计算出总路程 Total = 2 * (所有边的权重之和)。
2. 找到最大优惠: 找到从起点 1 出发，能到达的最远的城市。也就是计算出从节点 1 到所有其他节点的最长路径长度，取其中的最大值 Max_Path。
3. 最终答案: 用总成本减去这个最大的“优惠”，就是我们的最小总路程啦！Answer = Total - Max_Path。

那么，如何在一个树上找到从节点 1 出发的最长路径呢？因为是树形结构且边权都是正数，所以我们可以用一次简单的广度优先搜索（BFS）或者深度优先搜索（DFS）来计算出节点 1 到所有其他节点的距离，然后找到那个最大值就好啦！

代码实现，一起来敲键盘喵！

下面就是把我们的思路变成代码的时刻啦！这里用的是 BFS 的实现方式哦。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 为了防止数字太大溢出，我们用 long long 存路程，这是个好习惯哦~
typedef long long ll;

int main() {
    // 关闭同步流，让输入输出更快一点，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 如果只有一个城市，那就不需要走路啦，路程是0
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    // 用邻接表来存这棵可爱的树~ vector<pair<int, int>> 表示 {邻居节点, 边的权重}
    vector<vector<pair<int, int>>> graph(n + 1);
    ll total_weight_sum = 0;

    // 读入 n-1 条边
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        // 因为是无向边，所以两个方向都要加上
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
        // 累加所有边的权重
        total_weight_sum += w;
    }

    // 先把所有路都走两遍的总路程算出来
    ll total_path = 2LL * total_weight_sum;

    // dist数组，-1表示还没到过这个城市哦
    vector<ll> dist(n + 1, -1);
    // 用一个队列来进行广度优先搜索 (BFS) 呐
    queue<int> q;

    // 从起点1开始我们的旅程！
    dist[1] = 0;
    q.push(1);

    // BFS 过程，用来计算从1到所有其他点的最短（也是唯一）路径长度
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            // 如果邻居v还没被访问过
            if (dist[v] == -1) {
                // 更新v的距离，并把它加入队列等待探索
                dist[v] = dist[u] + w;
                q.push(v);
            }
        }
    }

    // 找到离起点1最远的那条路，这就是我们能省下的最大路程
    ll max_dist_from_start = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > max_dist_from_start) {
            max_dist_from_start = dist[i];
        }
    }

    // 总路程减去可以省掉的最长单程路，就是答案啦！
    cout << total_path - max_dist_from_start << endl;

    return 0;
}

复杂度分析时间！

这段代码跑得快不快呢？我们来分析一下，喵~

• 时间复杂度: O(N) 的说。 我们首先遍历了 N-1 条边来建图和计算总权重和，这是 O(N)。接着，我们进行了一次 BFS。在图中，BFS 会访问每个节点和每条边恰好一次，所以 BFS 的复杂度是 O(N + E)，其中 N 是节点数，E 是边数。因为这是棵树，所以 E = N-1。总的时间复杂度就是 O(N) + O(N + N-1) = O(N)，非常高效！

• 空间复杂度: O(N) 的说。 我们主要的空间开销是存储图的邻接表 graph，它需要 O(N + E) = O(N) 的空间。另外，dist 数组和 BFS 的队列 q 也都需要 O(N) 的空间。所以总的空间复杂度是 O(N)，完全可以接受！

知识点与总结 Kitty's Wisdom Corner

这道题真是又有趣又有启发性，主人 sama 一定也学到了很多吧！

1. 核心思想 - 贪心: 这道题的精髓在于“总成本 - 最大节省”的贪心思想。当我们面对一个看似复杂的最小化问题时，可以尝试把它转化为最大化一个“收益”或“节省”的部分。这种逆向思维在很多题目里都非常管用哦！

2. 图论模型 - 树: 题目描述中“任意两个城市之间都只有一条唯一的路径”是树结构的一个典型特征。快速识别出模型是解决图论问题的第一步，喵！

3. 树的路径问题: 在树上，从一个点到另一个点的路径是唯一的。因此，求单源最短路径（SSSP）就变得非常简单，直接用 BFS 或 DFS 就可以算出精确距离，不像在普通图里可能需要 Dijkstra 算法。

4. 编程技巧:

   • long long: 看到路径长度和节点数量都可能比较大时，要警惕整数溢出的风险，及时使用 long long 是个好习惯。
   • 邻接表: 对于稀疏图（特别是树），使用邻接表来存图比邻接矩阵要节省大量空间和时间。

希望这篇题解能帮到你，喵~ 如果还有其他问题，随时可以再来找我玩哦！我们一起变得更强，加油！(๑•̀ㅂ•́)و✧