倍增LCA

发表于 更新于

Too naiive 的我还是需要靠刷题获取人生经验

Bug找了半天

题目描述

A 国有 n 座城市，编号从 1 到 n ，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。对于不联通的两个城市，输出-1。

数据量：
0 < n < 10000, 0 < m < 50000, 0 < q < 30000

思路

题意也就是说要从一个图中找出一条路径连接两个城市，使这两个城市之间的道路的最小限重最大。

那么我们尽量不要去走小路，因为小路会拉低GDP……这题由于巨大的数据量，于是不能用最短路的算法来做。

经过琢磨，基本的思路还是有的：

如果能保证图连通性的情况下，不走小路。那么剩下的限重较大的路不多不少正好可以构成一棵支撑树（可能存在不联通的子图）。这第一步就是筛选符合要求的路喽，总体时间复杂度 O(nlog(n))。

经过第一步的筛选，复杂的道路已经所剩无几，接下来就是找两个点之间的最小连边。求树上两个节点之间的路径，这条路径一定会经过他们公共的父节点（父节点可能就是他们自身），这实际上就是 LCA（Least Common Ancestors） 问题。现在可以用dfs直接算吗？假设所有的城市连成一条线，而每次询问线段的两个端点那么需要的复杂度是 O(q*n)，妥妥TLE。所以朴素的做法还是不行的，为了A这道数据量大的题需要使用 倍增 的技巧。

倍增的主要思想就是用加倍的速度向上跳，而不是在树上一个节点一个节点得向上找。一般使用 2^n 加速，这样一来查询步骤的时间复杂度就将为 O(q*log(n))。

为了知道倍增地向上跳能跳到哪个祖先节点，得先构造一张跳跃表，也就是这里地 fa 数组，并且由于2^20远远大于n，所以数组开 [n][20] 足矣。更新方程是：

1
fa[j][i] = fa[fa[j][i-1]][i-1];

节点 j 的向上跳 2^i 次达到的祖先节点，可以看作是节点 j 向上跳 2^(i-1) 到达的祖先节点再向上跳 2^(i-1)。因为 2^i=2^(i-1) + 2^(i-1)。

更新两个节点之前最小路的方法也是类似，记w[j][i]表示节点j到它第 2^i 个祖先之间的最小的路，那么有等式：

1
w[j][i] = min(w[j][i-1], w[fa[j][i-1]][i-1]);

在跑LCA之前的初始化代码是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void dfs(int cur) {
    vis[cur] = true;
    // 遍历子节点
    for (int i = head[cur]; i; i = e[i].next) {
        int to = e[i].to;
        if (vis[to]) continue;
        deepth[to] = deepth[cur] + 1;
        fa[to][0] = cur;
        w[to][0] = e[i].v;
        dfs(to);
    }
}

void Deal() {
    // 由于可能存在多个子图，所以需要遍历每个可能脱离组织的节点
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            deepth[i] = 1;
            dfs(i);
            fa[i][0] = i;
            w[i][0] = INF;
        }
    }
    // 核心
    for (int i = 1; i <= 20; ++i) {
        for (int j = 1; j <= n; ++j) {
            fa[j][i] = fa[fa[j][i-1]][i-1];
            w[j][i] = min(w[j][i-1], w[fa[j][i-1]][i-1]);
        }
    }
}

最后是LCA的代码，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int LCA(int x, int y) {
    if (uni_find(x) != uni_find(y))
        return -1;
    int result = INF;
    if (deepth[x] < deepth[y]) {
        int t = x;
        x = y, y = t;
    }
    for (int i = 20; i >= 0; --i) {
        // 符合要求的上跳高度才向上跳
        if (deepth[fa[x][i]] >= deepth[y]) {
            result = min(result, w[x][i]);
            x = fa[x][i];
        }
    }
    if (x == y)
        return result;

    for (int i = 20; i >= 0; --i) {
        if (fa[x][i] != fa[y][i]) {
            result = min(result, min(w[x][i], w[y][i]));
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    // 最后不更新result会出错
    result = min(result, min(w[x][0], w[y][0]));
    return result;
}

小技巧

这里还有一个存图的技巧，之前存放节点数多但是连边稀疏的图都采用 vector，方便 + 稳定 = 慢。

所以出现了 __链式向前星__。

图示数据结构如下

物理数据结构如下

1
2
3
4
5
int head[MAXN]; // 邻接表表头
struct Edge {
    int to, next;
} e[MAXN << 1]; // 链表节点
int ptr = 0;    // 链表的指针

向链表中插入节点也很方便：

1
2
3
4
5
6
7
8
void add_edge(int from, int to) {
    ptr += 1;   // 使用下一个存放节点的空间
    e[ptr].to = to;
    
    // 将新节点放在表头位置
    e[ptr].next = head[from];
    head[from] = ptr;  
}