Network

题目描述：

给 \(N\) 个点的无向图 \(\left(1 \leq N \leq 15000\right)\), 记为： \(1\dots N\)
图中有 \(M\) 条边 \(\left(1\leq M \leq 30000\right)\) ,第 \(i\) 条边的长度记为 \(d_i \left(1 \leq d_i \leq 10 ^ 9 \right)\) ,现在有 \(K\) 个询问 \(\left(1 \leq K \leq 20000 \right)\) .每次询问查询从 \(A \rightarrow B\) 的所有路径中最长边的最小值

思路：

首先引入 \(Kruskal\) 重构树的概念。 \(Kruskal\) 重构树是基于最小生成树上建立的一个新树，构造的原理是将最小生成树的边权转变为该边所连的两个节点的公共祖先的点权。具体如下图。


那么最后的 \(Kruskal\) 重构树就是一个 $ 2n - 1 $ 个节点， \(2n - 2\) 条边的树。
同时 \(Kruskal\) 重构树具有一个很重要的性质：原图中两个点间所有路径上的边最大权值的最小值 \(=\) 最小生成树上两点简单路径的边最大权值 = \(Kruskal\) 重构树上两点 \(LCA\) 的点权。如果是求最小权值的最大值，就是最大生成树的基础上建重构树。
那么这个题就变成了 \(Kruskal\) 重构树的模板题

重构最小生成树

    struct node {
        int u, v, w;
        bool operator< (const node& lhs) const {
            return w < lhs.w;
        }
    }edge[N];

    int n, m, k, nn;
    int h[N], idx, val[N], e[N], ne[N];

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

    int fa[N]; 

    int find(int x) {
        return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
    }

    void kruskal() {
        for (int i = 1; i < N; i++) fa[i] = i;
        std::sort(edge + 1, edge + 1 + m);
        for (int i = 1; i <= m; i++) {
            int u = edge[i].u, v = edge[i].v, w = edge[i].w;
            if (find(u) == find(v)) continue;
            u = find(u), v = find(v);
            val[++n] = w;
            fa[n] = fa[u] = fa[v] = n;
            add(n, u), add(n, v);
        }
    }

树剖求 \(LCA\)

    int dep[N], siz[N], par[N], son[N], top[N];

    void dfs1(int u, int pa) {
        par[u] = pa, siz[u] = 1, dep[u] = dep[pa] + 1;
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v == pa) continue;
            dfs1(v, u);
            siz[u] += siz[v];
            if (siz[v] > siz[son[u]]) 
                son[u] = v;
        }
    }

    void dfs2(int u, int tp) {
        top[u] = tp;
        if (!son[u]) return ;
        dfs2(son[u], tp);
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v == par[u] || v == son[u]) continue;
            dfs2(v, v);
        }
    }

    int lca(int u, int v) {
        while(top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
            u = par[top[u]];
        }

        return dep[u] < dep[v] ? u : v;
    }

主函数

    signed main() {
        scanf("%d%d%d", &nn, &m, &k);
        n = nn;
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            edge[i] = {u, v, w};
        }

        kruskal();
        dfs1(n, 0);
        dfs2(n, n);

        for (int i = 0; i < k; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            printf("%d\n", val[lca(a, b)]);
        }

        return 0 ^ 0;
    }