AcWing 2863. 最短路 题解

题目分析

本题给定一个由(N)个点、(M)条边构成的仙人掌图，仙人掌图的定义为任意一条边至多只出现在一条简单回路的无向连通图。要求处理(Q)组询问，每组询问两个点，求出这两点之间的最短路径长度。

解题思路

本题通过Tarjan算法找出图中的环，将仙人掌图转化为类似树的结构，然后利用树上倍增求最近公共祖先（LCA）的方法来求解两点之间的最短路径。
1. 图的存储与初始化：使用邻接表存储图，h1用于存储原始仙人掌图，h2用于存储转化后的类似树的结构。add函数用于向邻接表中添加边。
2. 寻找环并转化图结构：tarjan函数利用Tarjan算法找出图中的环，对于不在环上的边直接添加到新图h2中；对于环上的边，通过build_circle函数重新构建环在新图中的连接方式，使得环上的点与一个新的虚拟点相连，且边权为环上路径的最短距离。
3. 树上倍增预处理：dfs_lca函数对转化后的树进行深度优先搜索，预处理每个节点的深度、父节点以及倍增数组fa，同时记录从根节点到每个节点的距离d。
4. 求最近公共祖先：lca函数使用倍增法求出两个节点的最近公共祖先，同时记录在求LCA过程中经过的两个节点A和B（在处理环上的情况时使用）。
5. 计算最短路径：在主函数中，对于每组询问，先求出两点的LCA。如果LCA是原图中的节点（即不在新添加的虚拟点中），则直接根据距离数组计算最短路径；如果LCA是虚拟点，则根据环上的距离信息计算最短路径。

代码逐段分析

1. 头文件和全局变量定义

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 12010, M = N * 3;

int n, m, Q, new_n;
int h1[N], h2[N], e[M], w[M], ne[M], idx;
int dfn[N], low[N], cnt;
int s[N], stot[N], fu[N], fw[N], fe[N];
int fa[N][14], depth[N], d[N];
int A, B;

• 引入必要的头文件，包括输入输出、字符串操作和算法相关的头文件。
• 定义常量(N)表示节点的最大数量，(M)表示边的最大数量。
• 变量(n)表示节点数，(m)表示边数，(Q)表示询问的组数，new_n用于记录新图中节点的数量（包括虚拟节点）。
• h1[N]和h2[N]是邻接表的头指针数组，e[M]存储边的另一端节点，w[M]存储边的权值，ne[M]指向下一条边的下标，idx用于记录边的编号。
• dfn[N]和low[N]用于Tarjan算法中记录节点的访问顺序和最早能回溯到的祖先节点的访问顺序，cnt用于计数。
• s[N]用于记录环上节点到环上某一点的距离，stot[N]用于记录环上节点到环上起点的总距离，fu[N]记录节点的父节点，fw[N]记录从父节点到当前节点的边权，fe[N]记录节点是由哪条边到达的（用于处理重边）。
• fa[N][14]是倍增数组，用于快速求最近公共祖先，depth[N]记录节点的深度，d[N]记录从根节点到当前节点的距离。

• A和B用于在求LCA过程中记录特定节点。

• 添加边函数

void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

• 该函数用于向邻接表h中添加一条从节点a到节点b，权值为c的边。

• 构建环在新图中的结构函数

void build_circle(int x, int y, int z)
{
    int sum = z;
    for (int k = y; k != x; k = fu[k])
    {
        s[k] = sum;
        sum += fw[k];
    }
    s[x] = stot[x] = sum;
    add(h2, x, ++ new_n, 0);
    for (int k = y; k != x; k = fu[k])
    {
        stot[k] = sum;
        add(h2, new_n, k, min(s[k], sum - s[k]));
    }
}

• 该函数用于处理环上的边，将环上的节点与一个新的虚拟点相连。
• 首先计算环上节点到环上某一点的距离sum，并记录在s[k]中。
• 添加一个新的虚拟点new_n，将环上的起点x与虚拟点相连，边权为(0)。

• 然后将环上其他节点与虚拟点相连，边权为该节点到环上起点的最短路径距离（通过min(s[k], sum - s[k])计算）。

• Tarjan算法函数

void tarjan(int u, int from)
{
    dfn[u] = low[u] = ++ cnt;
    for (int i = h1[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            fu[j] = u, fw[j] = w[i], fe[j] = i;  
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j]) add(h2, u, j, w[i]);
        }
        else if (i != (from ^ 1)) low[u] = min(low[u], dfn[j]);
    }
    for (int i = h1[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (dfn[u] < dfn[j] && fe[j] != i)
            build_circle(u, j, w[i]);
    }
}

• 该函数使用Tarjan算法找出图中的环。
• 初始化节点u的访问顺序dfn[u]和最早能回溯到的祖先节点的访问顺序low[u]。
• 遍历节点u的所有邻边：
  • 如果邻接节点j未被访问，记录其父节点、边权和到达边的信息，递归调用tarjan函数，并更新low[u]。如果dfn[u] < low[j]，说明这条边不在环上，将其添加到新图h2中。
  • 如果邻接节点j已被访问且不是从父节点过来的边，则更新low[u]。

• 再次遍历节点u的邻边，对于环上的边（根据dfn[u] < dfn[j]和fe[j] != i判断），调用build_circle函数处理环。

• 树上倍增预处理函数

void dfs_lca(int u, int father)
{
    depth[u] = depth[father] + 1;
    fa[u][0] = father;
    for (int k = 1; k <= 13; k ++ )
        fa[u][k] = fa[fa[u][k - 1]][k - 1];
    for (int i = h2[u]; ~i; i = ne[i])
    {
        int j = e[i];
        d[j] = d[u] + w[i];
        dfs_lca(j, u);
    }
}

• 该函数对转化后的树进行深度优先搜索，预处理节点的深度、父节点以及倍增数组。
• 更新节点u的深度为父节点深度加(1)，并记录其父节点。
• 通过倍增法计算fa[u][k]，即节点u向上(2^k)步的祖先节点。

• 遍历节点u的所有邻边，更新邻接节点j到根节点的距离d[j]，并递归处理邻接节点。

• 求最近公共祖先函数

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 13; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 13; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    A = a, B = b;
    return fa[a][0];
}

• 该函数使用倍增法求出节点a和节点b的最近公共祖先。
• 首先将a调整到与b深度相同（如果a的深度小于b，则将a向上移动）。
• 如果a和b相等，则返回a。
• 然后从大到小枚举k，如果fa[a][k]和fa[b][k]不相等，则将a和b同时向上移动(2^k)步。

• 记录最后一次不相等时的a和b（A和B），最后返回a的父节点，即最近公共祖先。

• 主函数

int main()
{
    scanf("%d%d%d", &n, &m, &Q);
    new_n = n;
    memset(h1, -1, sizeof h1);
    memset(h2, -1, sizeof h2);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(h1, a, b, c), add(h1, b, a, c);
    }
    tarjan(1, -1);

    dfs_lca(1, 0);

    while (Q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        if (p <= n) printf("%d\n", d[a] + d[b] - d[p] * 2);
        else
        {
            int da = d[a] - d[A], db = d[b] - d[B];
            int l = abs(s[A] - s[B]);
            int dm = min(l, stot[A] - l);
            printf("%d\n", da + dm + db);
        }
    }

    return 0;
}

• 读入节点数n、边数m和询问组数Q，初始化新图节点数new_n和邻接表头指针数组。
• 读入边的信息，构建原始仙人掌图的邻接表。
• 调用tarjan函数找出图中的环并构建新图结构。
• 调用dfs_lca函数进行树上倍增预处理。
• 对于每组询问：
  • 读入两个节点a和b，求出它们的最近公共祖先p。
  • 如果p是原图中的节点，则根据距离数组计算最短路径并输出。
  • 如果p是虚拟点，则根据环上的距离信息计算最短路径并输出。

时间复杂度分析

• Tarjan算法的时间复杂度为(O(M + N))，其中(M)是边数，(N)是节点数。
• 树上倍增预处理的时间复杂度为(O(N\log N))。
• 每次求LCA的时间复杂度为(O(\log N))，总共(Q)次询问，所以这部分时间复杂度为(O(Q\log N))。
• 总体时间复杂度为(O(M + N + N\log N + Q\log N))，由于(M)和(N)同阶，可近似认为时间复杂度为(O(N\log N + Q\log N))。

空间复杂度分析

主要空间消耗在于邻接表、各种辅助数组等，空间复杂度为(O(N + M)) 。