Description

题目链接

题目大意:$q$ 次询问图上两点间路径中边权最小值最大。

Solution

如果能走大的边,必然不会走小的。因此我们只需要对图建一棵最大生成树然后维护树上信息即可。

注意到图可能不连通,求的其实是最大生成森林。

之后问题变为树上两点间边权最小值,这个是树链剖分的基本运用,边权转点权之后码码码。时间复杂度 $O(n \log ^ 2 n)$。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

const int maxn = 1e4 + 10;
const int maxm = 5e4 + 10;

struct edge {
    int u, v;
    LL w;
    friend bool operator < (const edge &a, const edge &b) {
        return a.w > b.w;
    }
} e[maxm];

struct Edge {
    int to;
    LL w;
    Edge(const int &ito, const LL &iw) : to(ito), w(iw) {};
} ;

struct Node {
    int l, r;
    LL v;
} t[maxn << 2];

std::vector<Edge> g[maxn];
int top[maxn], dfn[maxn], w[maxn], fa[maxn], siz[maxn], son[maxn], dep[maxn], f[maxn], a[maxn];
int n, m, q, tot;

int unionFind(int x) { return f[x] == x ? x : f[x] = unionFind(f[x]); }

void dfs1(int x, int p) {
    dep[x] = dep[p] + 1;
    fa[x] = p;
    siz[x] = 1;
    for (auto i : g[x]) {
        if (i.to != p) {
            a[i.to] = i.w;
            dfs1(i.to, x);
            siz[x] += siz[i.to];
            if (siz[i.to] > siz[son[x]])    son[x] = i.to;
        }
    }
}

void dfs2(int x, int p) {
    top[x] = p;
    dfn[x] = ++tot;
    w[tot] = a[x];
    if (son[x]) {
        dfs2(son[x], p);
        for (auto i : g[x]) {
            if (i.to != fa[x] && i.to != son[x]) {
                dfs2(i.to, i.to);
            }
        }
    }
}

inline int lson(int x) { return x << 1; }
inline int rson(int x) { return x << 1 | 1; }

void buildTree(int x, int l, int r) {
    t[x].l = l, t[x].r = r;
    if (l == r) {
        t[x].v = w[l];
        return ;
    }
    int mid = (l + r) >> 1;
    buildTree(lson(x), l, mid), buildTree(rson(x), mid + 1, r);
    t[x].v = std::min(t[lson(x)].v, t[rson(x)].v);
}

int query(int x, int l, int r) {
    if (l <= t[x].l && t[x].r <= r)    return t[x].v;
    int min = 2e9, mid = (t[x].l + t[x].r) >> 1;
    if (l <= mid)    min = std::min(min, query(lson(x), l, r));
    if (r > mid)     min = std::min(min, query(rson(x), l, r));
    return min;
}

int queryMin(int u, int v) {
    int s = 2e9;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]])    std::swap(u, v);
        s = std::min(s, query(1, dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (dep[u] < dep[v])    std::swap(u, v);
    s = std::min(s, query(1, dfn[v] + 1, dfn[u]));
    return s;
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i)    f[i] = i;
    for (int i = 1; i <= m; ++i)    read(e[i].u), read(e[i].v), read(e[i].w);
    std::sort(e + 1, e + m + 1);
    for (int i = 1; i <= m; ++i) {
        int fu = unionFind(e[i].u), fv = unionFind(e[i].v);
        if (fu != fv) {
            f[fu] = fv;
            g[e[i].u].emplace_back(e[i].v, e[i].w), g[e[i].v].emplace_back(e[i].u, e[i].w);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            dfs1(i, 0);
            dfs2(i, i);
        }
    }
    buildTree(1, 1, n);
    read(q);
    while (q--) {
        int u, v;
        read(u), read(v);
        if (unionFind(u) != unionFind(v)) {
            puts("-1");
        } else {
            printf("%d\n", queryMin(u, v));
        }
    }
    return 0;
}
Last modification:September 2nd, 2021 at 02:05 am