洛谷P1967货车运输——倍增LCA

题目：https://www.luogu.org/problemnew/show/P1967

就是倍增LCA的裸题，注意一些细节即可。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const MAXN=,MAXM=,inf=1e9;

int n,m,q,dep[MAXN],pre[MAXN][],mn[MAXN][],ct1,ct=,head[MAXN];

int fa[MAXN],ans;

struct N{

    int hd,to,next,w;

    N(int h=,int t=,int n=,int w=):hd(h),to(t),next(n),w(w) {}

}edge[MAXM<<],ed[MAXM<<];

int find(int x)

{

    if(x==fa[x])return x;

    return fa[x]=find(fa[x]);

}

void add(int x,int y,int z)

{

    edge[++ct]=N(x,y,head[x],z);head[x]=ct;

    edge[++ct]=N(y,x,head[y],z);head[y]=ct;

}

void add1(int x,int y,int z)

{

    ed[++ct1]=N(x,y,,z);

}

bool cmp(N x,N y){return x.w>y.w;}

void kruskal()

{

    sort(ed+,ed+ct1+,cmp);

    for(int i=,u,v;i<=ct1;i++)

    {

        u=ed[i].to;

        v=ed[i].hd;

        int a=find(u);

        int b=find(v);

        if(a!=b)

        {

            add(u,v,ed[i].w);

            fa[a]=b;

        }

    }

}

void dfs(int x,int f)

{

    dep[x]=dep[f]+;

    pre[x][]=f;

    for(int i=head[x],u;i;i=edge[i].next)

    {

        u=edge[i].to;

        if(u==f)continue;

        mn[u][]=edge[i].w;

        dfs(u,x);

    }

}

void lca(int x,int y)

{

    int ans=inf;

    if(dep[x]>dep[y])swap(x,y);

    int d=dep[y]-dep[x];

    for(int i=;i<=;i++)

        if((d>>i)&)ans=min(ans,mn[y][i]),y=pre[y][i];//不是i-1！

    if(x==y)

    {

        printf("%d\n",ans);

        return;

    }

    for(int i=;i>=;i--)//不是i>0

    {

        if(pre[x][i]!=pre[y][i])

        {

            ans=min(ans,min(mn[x][i],mn[y][i]));

            x=pre[x][i];y=pre[y][i];

        }

    }

    ans=min(ans,min(mn[x][],mn[y][]));

    printf("%d\n",ans);

}

int main()

{

    int x,y,z;

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)

        scanf("%d%d%d",&x,&y,&z),add1(x,y,z);

    for(int i=;i<=n;i++)fa[i]=i;

    kruskal();

    for(int i=;i<=n;i++)

        if(!dep[i])dfs(i,);

    for(int j=;j<=;j++)

        for(int i=;i<=n;i++)

        {

            pre[i][j]=pre[pre[i][j-]][j-];

            mn[i][j]=min(mn[i][j-],mn[pre[i][j-]][j-]);

        }

    scanf("%d",&q);

    while(q--)

    {

        scanf("%d%d",&x,&y);

        if(find(x)!=find(y))printf("-1\n");

        else lca(x,y);

    }

    return ;

}