Connections between cities

1. 题目解析

这道题目是上一题（树上两点距离）的 变种和升级版。

关键差异与难点：

森林 (Forest) 结构：题目明确说“大部分道路被摧毁…不存在环路”。这意味着图不再是一棵完整的树，而是由多棵树组成的森林。
- 这意味着图可能不连通。
- 我们需要处理多个根节点。
连通性判断：题目要求如果两点不可达，输出 “Not connected”。
- 这意味着我们在查询 LCA 之前，必须先判断 $u$ 和 $v$ 是否在同一棵树上。
多组测试数据：输入包含多个实例，且没有给出具体的组数 $T$ ，通常需要使用 while(cin >> n >> m >> c) 来处理直到 EOF（文件结束）。
数据范围：
- $N \le 10000$ （比较小）。
- $C \le 1,000,000$ （查询非常多）。这要求查询必须是 $O(\log N)$ 或 $O(1)$ 的。

算法思路：

建图：依然使用链式前向星存储无向图。
森林的处理 (LCA Init 改良)：
- 普通的 LCA 模板只从一个固定的 root 开始 DFS。
- 对于森林，我们需要遍历所有点 $i = 1 \dots N$ 。
- 如果点 $i$ 还没被访问过（深度为 0），说明它是一个新连通块（新树）的根。
- 从这个 $i$ 开始 DFS，并给这棵树上的所有节点打上标记（例如 belong[u] = root_id）。
查询逻辑：
- 输入 $u, v$ 。
- 第一步：检查 belong[u] 是否等于 belong[v]。如果不等，直接输出 “Not connected”。
- 第二步：如果相等，套用公式 $Dist(u) + Dist(v) - 2 \times Dist(LCA(u, v))$ 。

2. 代码实现

基于你的模板进行了以下适配：

belong 数组：在 LCA 结构体中增加此数组，用来记录每个点属于哪棵树（即该树根节点的编号）。
init 函数改造：增加循环检测未访问节点，处理森林情况。
输入循环：使用 while(cin >> ...) 处理不定量的测试数据。
初始化重置：每次循环开始前调用 e.reset()，且在 init 中注意清空 d 数组以正确判断访问状态。

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-04 15:40:22
 * Problem: Forest Shortest Path (LCA on Forest)
 */
#include <bits/stdc++.h>
using namespace std;

const int maxn = 10005;   // N <= 10000
const int maxe = 20005;   // M < 10000, 双向边需要 x2

int n, m, c;

// === 1. 链式前向星 ===
struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn], edge_cnt;
    
    linkList(){ reset(); }
    
    // 多组数据，务必重置
    void reset() {
        edge_cnt = 0;
        memset(h, -1, sizeof(h));
    }
    
    void add2(int u, int v, int w) {
        e[edge_cnt] = {u, v, w, h[u]}; h[u] = edge_cnt++;
        e[edge_cnt] = {v, u, w, h[v]}; h[v] = edge_cnt++;
    }

    // 语法糖
#ifdef __cpp_range_based_for
    struct AdjIterator {
        int i; linkList* p;
        AdjIterator(linkList* p, int i) : p(p), i(i) {}
        AdjIterator& operator++() { i = p->e[i].next; return *this; }
        bool operator!=(const AdjIterator& oth) { return i != oth.i; }
        pair<int, int> operator*() { return {p->e[i].v, p->e[i].w}; }
    };
    struct BaseRange {
        int start; linkList* p;
        BaseRange(linkList* p, int start) : p(p), start(start) {}
        AdjIterator begin() { return AdjIterator(p, p->h[start]); }
        AdjIterator end()   { return AdjIterator(p, -1); }
    };
    BaseRange adj(int u) { return BaseRange(this, u); }
#endif
} e;

// === 2. LCA 模板 (支持森林 + 连通性检查) ===
const int MAXLOG = 15; // 2^14 > 10000 足够了
struct LCA {
    int f[maxn][MAXLOG + 1];
    int d[maxn];      // 深度
    int dis[maxn];    // 距离根的带权距离
    int belong[maxn]; // 记录点 u 属于哪棵树(存储根节点编号)

    // 初始化：处理森林
    void init(int n) {
        // 多组数据，d数组必须清零，作为visited标记使用
        memset(d, 0, sizeof(d)); 
        // f数组也清零比较安全
        memset(f, 0, sizeof(f));
        
        // 遍历所有点，处理森林中的每一棵树
        for(int i = 1; i <= n; ++i) {
            if(!d[i]) { // 如果深度为0，说明还没访问过，是一个新的连通块
                // 根节点的 belong 设为它自己，深度设为1，距离设为0
                dfs(i, 0, 1, 0, i);
            }
        }
        
        // 倍增预处理
        for (int j = 1; j <= MAXLOG; ++j) {
            for (int i = 1; i <= n; ++i) {
                f[i][j] = f[ f[i][j-1] ][ j-1 ];
            }
        }
    }

    // DFS: 增加 root_id 参数，标记连通分量
    void dfs(int u, int fa, int depth, int current_dist, int root_id) {
        d[u] = depth;
        f[u][0] = fa; 
        dis[u] = current_dist;
        belong[u] = root_id; // 标记阵营
        
        for (auto [v, w] : e.adj(u)) { 
            if (v != fa) {
                dfs(v, u, depth + 1, current_dist + w, root_id);
            }
        }
    }

    int ask_lca(int u, int v) {
        if (d[u] < d[v]) swap(u, v);
        for (int i = MAXLOG; i >= 0; --i) {
            if (d[u] - (1 << i) >= d[v]) u = f[u][i];
        }
        if (u == v) return u;
        for (int i = MAXLOG; i >= 0; --i) {
            if (f[u][i] != f[v][i]) {
                u = f[u][i];
                v = f[v][i];
            }
        }
        return f[u][0];
    }
    
    // 查询接口
    void query(int u, int v) {
        // 1. 连通性判断
        if (belong[u] != belong[v]) {
            cout << "Not connected\n";
            return;
        }
        
        // 2. 距离计算
        int l = ask_lca(u, v);
        int ans = dis[u] + dis[v] - 2 * dis[l];
        cout << ans << "\n";
    }

} lca;

int main() {
    // 必须优化IO，C 很大
    ios::sync_with_stdio(false); cin.tie(0);
    
    // 处理多组输入
    while(cin >> n >> m >> c) {
        e.reset(); // 清空边
        
        for(int i = 0; i < m; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            e.add2(u, v, w);
        }
        
        // 初始化 LCA (内部处理森林)
        lca.init(n);
        
        for(int i = 0; i < c; ++i) {
            int u, v;
            cin >> u >> v;
            lca.query(u, v);
        }
    }
    
    return 0;
}

Connections between cities

目录

1. 题目解析

2. 代码实现