Problem

给你 N 个点的无向图 (1 <= N <= 15,000)，记为：1…N。
图中有 M 条边 (1 <= M <= 30,000) ，第 j 条边的长度为： d_j (1 < = d_j < = 1,000,000,000).

现在有 K 个询问 (1 < = K < = 20,000)。
每个询问的格式是：A B，表示询问从 A 点走到 B 点的所有路径中，最长的边最小值是多少？

Solution

不再赘述。

传送门：https://www.cnblogs.com/ZegWe/p/6243883.html

感觉自己打得好傻逼...

Code

// Code by ajcxsu
// Problem: Network

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10, M=3e4+10;
struct Edge {
    int u,v,w;
} e[M];
bool cmp(const Edge &a, const Edge &b) { return a.w<b.w; }
int n,m,q;

int f[N],l[N],r[N],fa[N],w[N],p;
int Find(int x) {
    if(!fa[x]) return x;
    return fa[x]=Find(fa[x]);
}

int siz[N],dep[N],son[N],idx;
int dfn[N],top[N];
void dfs1(int x,int k) {
    dep[x]=k, siz[x]=1;


    if(l[x]!=0) {
        dfs1(l[x],k+1);
        siz[x]+=siz[l[x]];
        if(siz[l[x]]>siz[son[x]]) son[x]=l[x];
    }
    if(r[x]!=0) {
        dfs1(r[x],k+1);
        siz[x]+=siz[r[x]];
        if(siz[r[x]]>siz[son[x]]) son[x]=r[x];
    }
}
void dfs2(int x,int t) {
    dfn[x]=++idx;
    top[x]=t;
    if(son[x]) dfs2(son[x],t);
    if(l[x]!=son[x] && l[x]) dfs2(l[x],l[x]);
    if(r[x]!=son[x] && r[x]) dfs2(r[x],r[x]);
}

int lca(int s,int t) {
    while(top[s]!=top[t]) {
        if(dep[top[s]]<dep[top[t]]) swap(s,t);
        s=f[top[s]];
    }
    return dep[s]<dep[t]?s:t;
}


int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    p=n;
    for(int i=0;i<m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++) {
        int u=e[i].u, v=e[i].v;
        int af=Find(u), bf=Find(v);
        if(af==bf) continue;
        l[++p]=af, r[p]=bf;
        f[af]=f[bf]=fa[af]=fa[bf]=p;
        w[p]=e[i].w;
    }
    dfs1(p,1);
    dfs2(p,p);
    int u,v;
    for(int i=0;i<q;i++) {
        cin>>u>>v;
        cout<<w[lca(u,v)]<<endl;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-bzoj-3732.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆