lp1967 NOIP2013 货车运输

一道最大生成树加LCA的裸题。
因为是求路上权值最小的边权值最大，所以可以在最大生成树上跑。当然二分答案加01BFS也是一种想法，不过时间复杂度不对。
那么在最大生成树上很显然最大的路径上边权值最小。
所以在最大生成树上跑LCA，记录沿途路径最大值即可。
当然跑树剖也是可以的，不过很难写。

#include<iostream>
#include<cstdio>
#include<algorithm>

const int INF = 0x3f3f3f3f;

int n,m,q;

int FA[10005];
inline int fa( int X ){
    return X==FA[X]?X:(FA[X]=fa(FA[X]));
}
inline void mrg( int X, int Y ){
    X = fa( X ), Y = fa( Y );
    FA[X] = Y;
}

struct ee0{
    int u;
    int v;
    int w;
    inline bool operator < (const ee0 &B)const{
        return w > B.w;
    }
}e0[50005];

struct ee{
    int v;
    int w;
    int nxt;
}e[20005];
int h[10005],et=0;
inline void Add(int U,int V,int W){
    e[++et] = (ee){V,W,h[U]};
    h[U] = et;
}

int fi[10005][20],fv[10005][20],dep[10005];
bool vis[10005];
inline void dfs(int X,int FTHR){
    for(int i=h[X];i;i=e[i].nxt){
        if(vis[e[i].v]){
            continue;
        }
        vis[e[i].v]=1;
        fi[e[i].v][0]=X;
        fv[e[i].v][0]=std::min(fv[e[i].v][0],e[i].w);
        dep[e[i].v]=dep[X]+1;
        dfs(e[i].v,X);
    }
}

inline int lca(int X,int Y){
    dep[X]<dep[Y]?(X^=Y^=X^=Y):0;
    int ans=INF,dlt;
    if(X==Y){
        return 0;
    }
    for(dlt=15;dlt>=0;--dlt){
        if(dep[X]-(1<<dlt)>=dep[Y]){
            ans=std::min(ans,fv[X][dlt]);
            X=fi[X][dlt];
        }
    } 
    if(X==Y){
        return ans;
    }
    for(dlt=15;dlt>=0;--dlt){
        if(fi[X][dlt]!=fi[Y][dlt]){
            ans=std::min(ans,fv[X][dlt]);
            ans=std::min(ans,fv[Y][dlt]);
            X=fi[X][dlt],Y=fi[Y][dlt];
        }
    }
    ans=std::min(ans,fv[X][0]);
    ans=std::min(ans,fv[Y][0]);
    return ans;
}

void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&e0[i].u,&e0[i].v,&e0[i].w);
    }
    for(int i=1;i<=n;++i){
        FA[i]=i;
        fv[i][0]=INF;
    }
    std::sort(e0+1,e0+1+m);
    for(int i=1;i<=m;++i){
        if(fa(e0[i].v)!=fa(e0[i].u)){
            Add(e0[i].u,e0[i].v,e0[i].w);
            Add(e0[i].v,e0[i].u,e0[i].w);
            mrg(e0[i].u,e0[i].v);
        }
    }
    for(int i=1;i<=n;++i){
        if(FA[i]==i){
            fi[i][0]=0;
            fv[i][0]=0;
            vis[i]=1;
            dfs(i,0);
        }
    }
    scanf("%d",&q);
    for(int j=1;j<=15;++j){
        for(int i=1;i<=n;++i){
            fi[i][j]=fi[fi[i][j-1]][j-1];
            fv[i][j]=std::min(fv[i][j-1],fv[fi[i][j-1]][j-1]);
        }
    }
    int u,v;
    for(int i=1;i<=q;++i){
        scanf("%d%d",&u,&v);
        if(fa(u)!=fa(v)){
            puts("-1");
            continue;
        }
        printf("%d\n",lca(u,v));
    }
}

int main(){
    init();
    return 0;
}