【洛谷P1697】货车运输

首先，对于所有从x能到达y的路径中，限重越大越好 

因此我们用Kruskal最大生成树得到一片森林（不一定都联通）

之后dfs维护森林的深度和LCA的预处理limit[x][0]（x向上跳2^i步的边权最小值） 

对于每个询问，求x和y到lca的边权最小值即可

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 10010
#define M 100010
#define INF 100000000 
struct fx{
    int to,w,from,next;
    
}e[M],t[M];
int size,n,m,q,head[M],maxl[N],father[N];
int fa[N][25],limit[N][25],deep[N],vis[N];
void uni(int x,int y,int z){
    size++;
    e[size].to=y;
    e[size].from=x;
    e[size].w=z;
}
void Uni(int x,int y,int z){
    size++;
    t[size].next=head[x];
    head[x]=size;
    t[size].to=y;
    t[size].from=x;
    t[size].w=z;
}
bool cmp(fx a,fx b){
    return a.w>b.w;
}
int find(int x){
    if (father[x]!=x) father[x]=find(father[x]);
    return father[x];
}
void swap(int &x,int &y){
    int tmp;
    tmp=x;
    x=y;
    y=tmp;
}
void kruskal(){
    int x,y,r1,r2,cnt;
    for (int i=1;i<=n;i++)
        father[i]=i;
    sort(e+1,e+m+1,cmp);
    size=0;cnt=n;
    for (int p=1;p<=m&&cnt>1;p++){
        x=e[p].from;
        y=e[p].to;
        r1=find(x);
        r2=find(y);
        if (r1!=r2){
            father[r1]=r2;
            cnt--;
            Uni(x,y,e[p].w);
            Uni(y,x,e[p].w);
        }
    }
}
void dfs(int x,int xx){
    vis[x]=1;
    fa[x][0]=xx;
    for (int k=head[x];k;k=t[k].next){
        int y=t[k].to;
        if (y==xx) continue;
        deep[y]=deep[x]+1;
        limit[y][0]=t[k].w;
        dfs(y,x);
    }
}
void Limit(){
    for (int j=1;j<=20;j++)
        for (int i=1;i<=n;i++){
            limit[i][j]=min(limit[fa[i][j-1]][j-1],limit[i][j-1]);
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
}
int LCA(int x,int y){
    int d,minl=INF;
    if (deep[x]<deep[y])
        swap(x,y);
    d=deep[x]-deep[y];
    for (int i=0;i<=20;i++)
        if ((1<<i)&d) {
            minl=min(minl,min(limit[x][i],limit[x][0]));
            x=fa[x][i];
        }
    if (x==y) return minl;//相等则不需向上跳   
    for (int i=20;i>=0;i--)
        if (fa[x][i]!=fa[y][i]){
            minl=min(minl,min(limit[x][i],limit[y][i]));
            x=fa[x][i];
            y=fa[y][i];
        }
    minl=min(minl,min(limit[x][0],limit[y][0]));
    return minl;
}
int main(){
    int x,y,z,r1,r2;
    size=0;
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%d %d %d",&x,&y,&z);
        uni(x,y,z);
    }
    kruskal();
    for (int i=1;i<=n;i++) 
        if (!vis[i]){
            deep[i]=1;
            dfs(i,0);//森林  
        }
    Limit();
    scanf("%d",&q);
    for (int i=1;i<=q;i++){
        scanf("%d %d",&x,&y);
        r1=find(x);
        r2=find(y);
        if (r1!=r2) printf("-1\n");
        else printf("%d\n",LCA(x,y));
    }
    return 0;
}