P3247 [HNOI2016]最小公倍数 题解

· · 题解

题意

给定一张 n 个点 m 条边的无向图 (1\le n\le 5\cdot10^4, 1\le m\le 10^5)，每条边有两个权值 a_e, b_e。有 q 次询问，每次询问两个点之间是否存在一条（不一定简单的）路径使得路径上两种边权的最大值分别等于给定值。

题解

容易发现有用的边满足两种权值都不超过询问，把有用的边加入之后检查两个点是否在同一个连通块以及两种权值的最大值是否分别等于询问的值即可。

先将边按照 a_e 排序并分块。把每个询问放到最后一个满足下列条件的块：前面块的 a_e 都不超过询问的 a。这样对每个询问有用的边就只有前面的块和它所在的块。

依次处理每个块，由于前面块的 a_e 都不超过询问的 a，所以只需要考虑 b。把前面块的所有边和当前块的询问都按照 b 排序，处理每个询问的时候把不超过询问的 b 的边都加入即可。用路径压缩和启发式合并的并查集维护，每次操作时间复杂度 O(\alpha(n))。

对于块内的边，暴力将所有有用的边加入，进行一次 BFS 即可回答询问。

设块大小为 B，时间复杂度为 O((qB+\frac{m^2}B)\alpha(n))。取 B=O(\frac{m}{\sqrt q})，则时间复杂度为 O(m\sqrt q\alpha(n))。

代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 50'000, M = 100'000, Q = 50'000;
struct Edge {
    int u, v, a, b;
};
struct Query {
    int u, v, a, b, id;
};
int fa[N], mxa[N], mxb[N];
Edge edge[M];
vector<Query> query[M];
vector<tuple<int, int, int>> e[N];
int id[N], stk[N], que[N];
bool ans[Q], vis[N], used[N];
int find(int x) {
    while (fa[x] >= 0 && fa[fa[x]] >= 0)
        x = fa[x] = fa[fa[x]];
    return fa[x] >= 0 ? fa[x] : x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m;
    memset(id, -1, n * sizeof(int));
    for (int i = 0; i < m; ++i) {
        cin >> edge[i].u >> edge[i].v >> edge[i].a >> edge[i].b;
        --edge[i].u;
        --edge[i].v;
    }
    sort(edge, edge + m, [&](const Edge &lhs, const Edge &rhs) {
        return lhs.a < rhs.a;
    });
    cin >> q;
    int sz = 1.5 * m / sqrt(q);
    int blocks = (m + sz - 1) / sz;
    for (int i = 0; i < q; ++i) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        --u;
        --v;
        int j = 0;
        while (j + 1 < blocks && edge[sz * j + sz - 1].a <= a)
            ++j;
        query[j].push_back(Query{u, v, a, b, i});
    }
    for (int bl = 0; bl < blocks; ++bl) {
        memset(fa, -1, n * sizeof(int));
        memset(mxa, -1, n * sizeof(int));
        memset(mxb, -1, n * sizeof(int));
        int i = 0;
        sort(edge, edge + sz * bl, [&](const auto &lhs, const auto &rhs) {
            return lhs.b < rhs.b;
        });
        sort(query[bl].begin(), query[bl].end(), [&](const auto &lhs, const auto &rhs) {
            return lhs.b < rhs.b;
        });
        for (auto &&q : query[bl]) {
            while (i < sz * bl && edge[i].b <= q.b) {
                int u = find(edge[i].u);
                int v = find(edge[i].v);
                if (u != v) {
                    if (fa[u] > fa[v])
                        swap(u, v);
                    fa[u] += fa[v];
                    mxa[u] = max(mxa[u], mxa[v]);
                    mxb[u] = max(mxb[u], mxb[v]);
                    fa[v] = u;
                }
                mxa[u] = max(mxa[u], edge[i].a);
                mxb[u] = max(mxb[u], edge[i].b);
                ++i;
            }
            int stkTop = 0;
            int u = find(q.u);
            used[u] = true;
            stk[stkTop++] = u;
            int v = find(q.v);
            if (u != v) {
                used[v] = true;
                stk[stkTop++] = v;
            }
            for (int j = sz * bl; j < m && j < sz * (bl + 1); ++j) {
                if (edge[j].a <= q.a && edge[j].b <= q.b) {
                    int u = find(edge[j].u);
                    int v = find(edge[j].v);
                    if (!used[u]) {
                        used[u] = true;
                        stk[stkTop++] = u;
                    }
                    if (!used[v]) {
                        used[v] = true;
                        stk[stkTop++] = v;
                    }
                    e[u].emplace_back(v, edge[j].a, edge[j].b);
                    e[v].emplace_back(u, edge[j].a, edge[j].b);
                }
            }
            int queL = 0, queR = 0;
            que[queR++] = u;
            vis[u] = true;
            int ma = -1, mb = -1;
            while (queL < queR) {
                int u = que[queL++];
                ma = max(ma, mxa[u]);
                mb = max(mb, mxb[u]);
                for (auto &&ed : e[u]) {
                    int v, a, b;
                    tie(v, a, b) = ed;
                    ma = max(ma, a);
                    mb = max(mb, b);
                    if (!vis[v]) {
                        vis[v] = true;
                        que[queR++] = v;
                    }
                }
            }
            ans[q.id] = vis[v] && ma == q.a && mb == q.b;
            for (int j = 0; j < stkTop; ++j) {
                int u = stk[j];
                used[u] = vis[u] = false;
                e[u].clear();
            }
        }
    }
    for (int i = 0; i < q; ++i)
        cout << (ans[i] ? "Yes" : "No") << "\n";
    return 0;
}