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

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

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

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const MAXN=10005,MAXM=50005,inf=1e9;
int n,m,q,dep[MAXN],pre[MAXN][20],mn[MAXN][20],ct1,ct=1,head[MAXN];
int fa[MAXN],ans;
struct N{
    int hd,to,next,w;
    N(int h=0,int t=0,int n=0,int w=0):hd(h),to(t),next(n),w(w) {}
}edge[MAXM<<1],ed[MAXM<<1];
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,0,z);
}
bool cmp(N x,N y){return x.w>y.w;}
void kruskal()
{
    sort(ed+1,ed+ct1+1,cmp);
    for(int i=1,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]+1;
    pre[x][0]=f;
    for(int i=head[x],u;i;i=edge[i].next)
    {
        u=edge[i].to;
        if(u==f)continue;
        mn[u][0]=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=0;i<=17;i++)
        if((d>>i)&1)ans=min(ans,mn[y][i]),y=pre[y][i];//不是i-1！ 
    if(x==y)
    {
        printf("%d
",ans);
        return;
    }
    for(int i=17;i>=0;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][0],mn[y][0]));
    printf("%d
",ans);
}
int main()
{
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&x,&y,&z),add1(x,y,z);
    for(int i=1;i<=n;i++)fa[i]=i;
    kruskal();
    for(int i=1;i<=n;i++)
        if(!dep[i])dfs(i,0);
    for(int j=1;j<=17;j++)
        for(int i=1;i<=n;i++)
        {
            pre[i][j]=pre[pre[i][j-1]][j-1];
            mn[i][j]=min(mn[i][j-1],mn[pre[i][j-1]][j-1]);
        }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&x,&y);
        if(find(x)!=find(y))printf("-1
");
        else lca(x,y);
    }
    return 0;
}