F. The Shortest Statement - 题解

比赛与标签

比赛: Educational Codeforces Round 51 (Rated for Div. 2) 标签: graphs, shortest paths, trees, *2400 难度: *2400

题目到底在说什么喵？

哈喵~ 各位算法大师们好呀！今天我们来解决一个很有趣的图论问题哦！

题目是这样子的：我们拿到一个有 n 个点和 m 条边的带权无向连通图。然后呢，会有 q 次询问，每次询问都会给我们两个点 u 和 v，需要我们找出它们之间的最短路径长度是多少的说。

输入输出很简单：

• 先是点数 n 和边数 m。
• 接着是 m 条边的信息（连接的两个点和边的权重）。
• 然后是询问次数 q。
• 最后是 q 组询问，每组包含两个点 u 和 v。

最最最关键的信息，也是解题的突破口，藏在一个小小的限制里：m - n <= 20！看到这个是不是眼前一亮呀？这可是重要的提示喵~

猫娘的思考回路~

这个 m - n <= 20 的限制实在是太可疑了，对吧？让本猫娘来分析一下！

一个有 n 个点的连通图，最少需要 n-1 条边才能连通，这个时候它就是一棵树，对不对？我们的图有 m 条边，那么 m - (n-1) 就代表了比一棵树“多”出来的边的数量。根据题目条件 m - n <= 20，我们可以推断出 m - (n-1) <= 21。

这意味着，我们的图本质上是一棵巨大的生成树，上面额外挂了最多 21 条边！这些额外的边会在树上形成一些环，但数量非常少。这就像一个巨大的猫爬架（生成树），上面只多了几个小小的装饰品（额外的边）呢！

既然图的主体是树，那我们就可以从这里下手啦！

1. 拆分图结构 我们可以先把图中的一棵生成树 T 找出来，剩下的就是那些“额外”的边了。怎么找呢？从任意一个点（比如1号点）开始做一次深度优先搜索（DFS），走过的边就构成了我们的生成树 T。在DFS过程中，如果遇到一个已经访问过的点（并且不是当前节点的父节点），那么连接当前点和这个已访问点的边就是一条“额外”的边啦。

2. “特殊点” S 这些“额外”的边连接的端点，我们把它们叫做“特殊点”，记作集合 S。因为最多只有 21 条额外边，所以特殊点的数量 |S| 最多也就是 2 * 21 = 42 个。哇，这个数量好小呀，我们可以对它们做一些预处理的说！

3. 分析最短路径 对于任意两个查询点 u 和 v，它们之间的最短路径可能有两种情况：

   • 情况一： 最短路径完全由生成树 T 上的边构成。这种情况下，路径长度就是它们在树上的距离。这个距离可以用 LCA (最近公共祖先) 快速计算出来。我们可以预处理每个点到树根的距离 dist_root[i]，那么 dist_T(u, v) = dist_root[u] + dist_root[v] - 2 * dist_root[lca(u, v)]。
   • 情况二： 最短路径经过了至少一条“额外”的边。任何一条经过额外边的路径，都可以看成是这样的形式：u 先通过树边走到某个特殊点 s_i，然后通过图中的路径（可能包含树边和其他额外边）走到另一个特殊点 s_j，最后再从 s_j 通过树边走到 v。 即： u --(树上路径)--> s_i --(图中真实最短路)--> s_j --(树上路径)--> v

4. 整合思路与预处理 结合上面的分析，我们可以得到最终的求解公式： dist(u, v) = min( dist_T(u, v), min_{s_i, s_j ∈ S} (dist_T(u, s_i) + dist_G(s_i, s_j) + dist_T(s_j, v)) ) 其中：

   • dist_T(a, b) 是 a 和 b 在生成树 T 上的距离，可以通过LCA在 O(log n) 时间内求出。
   • dist_G(s_i, s_j) 是特殊点 s_i 和 s_j 在原图 G 中的真实最短路。

   现在的问题就剩下如何求出所有特殊点对 (s_i, s_j) 之间的最短路 dist_G(s_i, s_j) 了。 因为特殊点 S 的数量 k 非常小（k <= 42），我们可以为它们建立一个 k x k 的邻接矩阵。

   • 首先，用它们在生成树 T 上的距离 dist_T(s_i, s_j) 来初始化这个矩阵。
   • 然后，对于每一条额外边 (u, v, w)（其中 u, v 必然是特殊点），我们用 w 来更新 dist_G(u, v) 和 dist_G(v, u) 的值（取更小者）。
   • 最后，在这个 k x k 的矩阵上跑一遍 Floyd-Warshall 算法，就能得到所有特殊点对之间的最短路径啦！O(k^3) 的复杂度对于 k <= 42 来说是小菜一碟！

   预处理步骤总结:

   1. DFS 建立生成树 T，同时找出所有额外边及其端点（特殊点集合 S）。
   2. 对生成树 T 进行预处理，以便用LCA快速查询树上距离。
   3. 对特殊点集合 S，计算它们两两之间的最短路 dist_G，并存起来。

   查询步骤总结:

   1. 对于查询 (u, v)，先计算树上距离 dist_T(u, v) 作为初始答案。
   2. 遍历所有特殊点对 (s_i, s_j)，用 dist_T(u, s_i) + dist_G(s_i, s_j) + dist_T(s_j, v) 更新答案。

这样，我们就能高效地回答所有查询了，喵~

魔法代码全解析！

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <set>
#include <map>

using namespace std;

// 常量定义，数组大小和无穷大的说
const int N = 100005;
const int LOGN = 18; // log2(100005) 向上取整是17，18很安全喵
const int MAX_S = 44; // m-n <= 20 -> m-(n-1) <= 21 条额外边 -> |S| <= 42。44很安全喵~

// 全局变量区
int n, m;
vector<pair<int, int>> adj[N]; // 邻接表存图
vector<tuple<int, int, int>> extra_edges; // 存放非树边

// LCA 相关的数据结构
int parent[N][LOGN]; // 用于二进制提升的父节点数组
int depth[N];        // 节点深度
long long dist_root[N]; // 节点到树根的距离（在生成树上）

// 特殊点相关的数据
vector<int> S_vec;      // 存储特殊点的vector
map<int, int> S_map;    // 特殊点到其在S_vec中索引的映射

// 预计算好的特殊点之间的最短路矩阵
long long dist_S_matrix[MAX_S][MAX_S];

// DFS用的访问标记数组
bool visited[N];

// DFS函数，用来构建生成树并找出所有非树边
// 同时计算深度、LCA的父节点、以及在树上到根的距离
void find_spanning_tree_dfs(int u, int p, int d, long long current_dist) {
    visited[u] = true;
    depth[u] = d;
    parent[u][0] = p;
    dist_root[u] = current_dist;

    for (auto& edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v == p) continue; // 不走回头路
        if (visited[v]) {
            // 这是一条返祖边，也就是我们说的“额外”边
            // u < v 的判断是为了保证每条无向边只被添加一次
            if (u < v) {
                extra_edges.emplace_back(u, v, w);
            }
        } else {
            // 这是一条树边，继续DFS
            find_spanning_tree_dfs(v, u, d + 1, current_dist + w);
        }
    }
}

// 预处理LCA的二进制提升表
void build_lca() {
    for (int k = 1; k < LOGN; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (parent[i][k-1] != 0) {
                parent[i][k] = parent[parent[i][k-1]][k-1];
            }
        }
    }
}

// 查询两个点 u 和 v 的最近公共祖先
int get_lca(int u, int v) {
    // 保证 u 的深度不小于 v
    if (depth[u] < depth[v]) swap(u, v);
    
    // 将 u 提升到和 v 同样的深度
    for (int k = LOGN - 1; k >= 0; --k) {
        if (parent[u][k] != 0 && depth[parent[u][k]] >= depth[v]) {
            u = parent[u][k];
        }
    }

    if (u == v) return u;

    // u 和 v 一起向上跳，直到它们的父节点相同
    for (int k = LOGN - 1; k >= 0; --k) {
        if (parent[u][k] != 0 && parent[v][k] != 0 && parent[u][k] != parent[v][k]) {
            u = parent[u][k];
            v = parent[v][k];
        }
    }
    return parent[u][0];
}

// 计算 u 和 v 在生成树 T 上的距离
long long get_dist_T(int u, int v) {
    int lca = get_lca(u, v);
    return dist_root[u] + dist_root[v] - 2 * dist_root[lca];
}

int main() {
    // 加速输入输出，是个好习惯喵
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    // --- 预处理阶段 ---

    // 1. 用DFS找到一棵生成树，并识别出所有额外边
    // 因为图是连通的，从节点1开始的一次DFS就足够了
    find_spanning_tree_dfs(1, 0, 0, 0);

    // 2. 预处理LCA的二进制提升表
    build_lca();

    // 3. 收集所有额外边的端点，构成特殊点集合 S
    set<int> S_set;
    for (auto& edge : extra_edges) {
        S_set.insert(get<0>(edge));
        S_set.insert(get<1>(edge));
    }
    for (int s_node : S_set) {
        S_map[s_node] = S_vec.size();
        S_vec.push_back(s_node);
    }
    int k_S = S_vec.size(); // 特殊点的数量

    // 4. 构建特殊点之间的辅助图，并计算所有点对的最短路
    // 首先，用树上距离初始化距离矩阵
    for (int i = 0; i < k_S; ++i) {
        for (int j = 0; j < k_S; ++j) {
            dist_S_matrix[i][j] = get_dist_T(S_vec[i], S_vec[j]);
        }
    }

    // 然后，用额外边的权重来更新这个矩阵
    for (auto& edge : extra_edges) {
        int u, v, w;
        tie(u, v, w) = edge;
        int u_idx = S_map[u];
        int v_idx = S_map[v];
        dist_S_matrix[u_idx][v_idx] = min(dist_S_matrix[u_idx][v_idx], (long long)w);
        dist_S_matrix[v_idx][u_idx] = min(dist_S_matrix[v_idx][u_idx], (long long)w);
    }

    // 5. 运行Floyd-Warshall算法，得到特殊点之间在原图中的真实最短路
    for (int k = 0; k < k_S; ++k) {
        for (int i = 0; i < k_S; ++i) {
            for (int j = 0; j < k_S; ++j) {
                dist_S_matrix[i][j] = min(dist_S_matrix[i][j], dist_S_matrix[i][k] + dist_S_matrix[k][j]);
            }
        }
    }

    // --- 回答查询阶段 ---
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;

        // 初始答案是它们在树上的距离
        long long ans = get_dist_T(u, v);

        // 如果存在特殊点，就考虑经过它们的路径
        if (k_S > 0) {
            vector<long long> dist_u_S(k_S);
            vector<long long> dist_v_S(k_S);
            // 计算 u, v 到所有特殊点的树上距离
            for (int i = 0; i < k_S; ++i) {
                dist_u_S[i] = get_dist_T(u, S_vec[i]);
                dist_v_S[i] = get_dist_T(v, S_vec[i]);
            }

            // 遍历所有特殊点对 (s_i, s_j)，尝试更新答案
            // 路径形如 u --(T)--> s_i --(G)--> s_j --(T)--> v
            for (int i = 0; i < k_S; ++i) {
                for (int j = 0; j < k_S; ++j) {
                    ans = min(ans, dist_u_S[i] + dist_S_matrix[i][j] + dist_v_S[j]);
                }
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

复杂度分析喵

• 时间复杂度: O(n log n + q * (k * log n + k^2)) 的说。

  • 预处理：
    • DFS建树和找边是 O(n + m)。
    • LCA的二进制提升表预处理是 O(n log n)。
    • 初始化特殊点距离矩阵需要 k^2 次LCA查询，是 O(k^2 log n)。
    • Floyd-Warshall是 O(k^3)。
    • 所以预处理总共是 O(n log n + k^2 log n + k^3)。因为 k 很小（k <= 42），所以这部分主要是 O(n log n)。
  • 查询：
    • 每次查询，计算 u 和 v 到所有 k 个特殊点的树上距离需要 O(k log n)。
    • 之后遍历所有特殊点对 (s_i, s_j) 需要 O(k^2)。
    • 所以单次查询是 O(k log n + k^2)。
    • q 次查询就是 O(q * (k log n + k^2)) 啦。

• 空间复杂度: O(n log n) 的说。

  • 邻接表 adj 是 O(n + m)。
  • LCA的 parent 数组是 O(n log n)。
  • 其他如 dist_S_matrix 等都是 O(k^2) 或者 O(n)，k 是个小常数。
  • 所以空间瓶颈在于LCA的预处理，是 O(n log n)。

知识点与总结

这道题真是一次美妙的思维探险呐！它教会了我们：

1. 观察题目限制：m - n <= 20 是解题的“金钥匙”！它强烈暗示了图的结构是“树 + 少量边”，引导我们向这个方向思考。
2. 图论问题的转化：我们成功地把一个在普通图上求多组最短路的问题，转化为了“树上路径查询”和“少量特殊点之间的小规模全源最短路”两个子问题，大大降低了复杂度。这种“抓主要矛盾（树结构），处理次要矛盾（额外边）”的思想非常重要！
3. 算法组合拳：这道题综合运用了 DFS (建树)、LCA (树上距离)、Floyd-Warshall (全源最短路) 等多种经典算法，是一次很好的练习机会。
4. 特殊点思想：当问题中的某些点（比如额外边的端点）具有特殊性质且数量不多时，可以围绕它们进行预处理和计算，这是一种非常强大的解题策略。

希望这次的题解能帮到你哦！如果还有不明白的地方，随时可以再来问本猫娘~ 一起加油，变得更强吧！喵~ >w<