题解

「from CommonAnts」寻找 LCR

题目描述

给你一个 $n$ 个点 $m$ 条边的无向连通图,编号为 $1$ 到 $n$ ,没有自环,可能有重边,每一条边有一个正权值 $w$ 。给出 $q$ 个询问,每次给出两个不同的点 $u$ 和 $v$ ,求一条从 $u$ 到 $v$ 的路径上边权的最大值最小是多少。

数据范围

$n \leq 70000,m \leq 100000, q \leq 10000000$.

题目链接

loj6021

题解

说白了就是求最小瓶颈路。
然而
评测记录
事情并没有那么简单。。。
因为数据范围有点鬼畜,询问次数已经要求算法必须实现 $O(1)$ 查询了。
常规做法已经没有可以优化的地方了。
所以我们必须另辟蹊径,采用 $Kruscal$ 重构树,因为 $Kruscal$ 树中两点的最大值就是 $LCA$ 的点权。
不过只是这样的话还是没有什么意义,查询的时间复杂度还是 $O(q \log_2 {q} )$ 的。
用 $Kruscal$ 重构树(这东西还挺偏的,但是 $\text{NOI2018\ Day1\ T1}$ 就可以用这个做。。。)的最大的好处是只要知道 $LCA$ 就可以了,而不必知道中间经过了哪些点,不需要求那些边的最大值。
$Kruscal$ 重构树的性质和求法我先咕咕咕了,以后单独写篇学习笔记吧(咕咕咕)。
那我们把求原来的倍增求树上两点间的最大值换成可以 $O(1)$ 查询$LCA$ 的欧拉序 + $ST$ 表,就可以 $AC$ 了。

PS

双倍经验

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
const int MAXN = 3e5 + 7;
const int HA = 1e9 + 7;
int A,B,C,P;
inline int rnd(){return A=(A*B+C)%P;}
struct Edge {
    int s, t, w, next;
    bool operator < (const Edge &other) const {
        return w < other.w;
    }
} edge[MAXN << 1], node[MAXN];
int head[MAXN], cnt, tot;
int n, m, q;
int f[MAXN][22], w[MAXN], dfn[MAXN], deep[MAXN], ts, lg2[MAXN];
int fa[MAXN], h[MAXN];
long long ans = 0;
inline void add(int u, int v) {
    edge[++cnt] = (Edge){u, v, 0, head[u]}; head[u] = cnt;
}
inline int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void read(int &x) {
    int flag = 1, ret = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        ret = ret * 10 + ch - '0';
        ch = getchar();
    }
    x = ret * flag;
}
void init(int u, int pre) {
    dfn[u] = ++ts;
    deep[u] = deep[pre] + 1;
    f[ts][0] = u;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        init(v, u);
        f[++ts][0] = u;
    }
}
inline void prepare() {
    for (int i = 2; i <= ts; i++) lg2[i] = lg2[i >> 1] + 1;
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i + (1 << j) - 1 <= ts; i++) {
            f[i][j] = deep[f[i][j - 1]] < deep[f[i + (1 << j - 1)][j - 1]] ? f[i][j - 1] : f[i + (1 << j - 1)][j - 1];
        }
    }
}
inline int getLca(int u, int v) {
    int l = dfn[u], r = dfn[v];
    if (l > r) std::swap(l, r);
    int k = lg2[r - l + 1];
    return deep[f[l][k]] < deep[f[r - (1 << k) + 1][k]] ? f[l][k] : f[r - (1 << k) + 1][k];
}
int main(int argc, char *argv[]) {
    read(n), read(m);
    for (int i = 1; i <= 2 * n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        read(node[i].s), read(node[i].t), read(node[i].w);
    }
    std::sort(node + 1, node + m + 1);
    tot = n;
    for (int i = 1; i <= m; i++) {
        int u = find(node[i].s), v = find(node[i].t);
        if (u == v) continue;
        w[++tot] = node[i].w;
        add(tot, u), add(tot, v);
        fa[u] = fa[v] =  tot;
    }
    init(tot, 0);
    prepare();
    read(q);
    read(A), read(B), read(C), read(P);
    int u, v;
    for (int i = 1; i <= q; i++) {
        u = rnd() % n + 1, v = rnd() % n + 1;
        ans += w[getLca(u, v)];
        if (ans >= HA) ans -= HA;
    }
    printf("%lld\n", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注