P1967 题解

· · 题解

题目传送门

思路

不难发现，当有两条路径同时满足从 x 到 y，肯定会优先选择载重量较大的一条路径。然后想到可以把载重量小的边全部删掉，得到一棵最大生成树。

得到了一棵树，不难想到用 LCA 倍增求最终答案。

时间复杂度 \mathcal{O}(n\log n)，可以通过此题。

注意事项

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e4+10,M=5e4+10;
int n,m,fa[N],depth[N],dp[40][N],w[40][N];
void _init(){
    for(int i=1;i<=n;++i)
        fa[i]=i;
    return;
}
int _find(int x){
    if(x==fa[x])
        return x;
    fa[x]=_find(fa[x]);
    return fa[x];
}
void _merge(int x,int y){
    int xx=_find(x),yy=_find(y);
    if(xx!=yy)
        fa[xx]=yy;
    return;
}
struct node{
    int u,v,w;
    friend bool operator<(const node cmp_x,const node cmp_y){
        return cmp_x.w>cmp_y.w;
    }
}a[M];
vector<node>vc[N];
void kruskal(){
    sort(a+1,a+m+1);
    _init();
    int cnt=0,sum=0;
    for(int i=1;i<=m;++i){
        if(cnt==n-1)
            break;
        if(_find(a[i].u)!=_find(a[i].v)){
            _merge(a[i].u,a[i].v),++cnt;
            vc[a[i].u].push_back({a[i].u,a[i].v,a[i].w});
            vc[a[i].v].push_back({a[i].v,a[i].u,a[i].w});
        }
    }
    return;
}
#define fa father
void dfs(int x,int fa){
    depth[x]=depth[fa]+1;
    dp[0][x]=fa;
    for(int i=1;i<=30;++i){
        dp[i][x]=dp[i-1][dp[i-1][x]];
        w[i][x]=min(w[i-1][x],w[i-1][dp[i-1][x]]);
    }
    for(auto i:vc[x])
        if(i.v!=fa){
            w[0][i.v]=i.w;
            dfs(i.v,x);
        }
    return;
}
#undef fa
int lca(int x,int y){
    if(_find(x)!=_find(y))
        return -1;
    if(depth[x]<depth[y])
        swap(x,y);
    int h=depth[x]-depth[y],ans=INT_MAX;
    for(int i=30;i>=0;--i)
        if(h>=(1<<i)){
            h-=(1<<i);
            ans=min(ans,w[i][x]);
            x=dp[i][x];
        }
    if(x==y)
        return ans;
    for(int i=30;i>=0;--i)
        if(dp[i][x]!=dp[i][y]&&(1<<i)<=depth[x]){
            ans=min(ans,w[i][x]);
            x=dp[i][x];
            ans=min(ans,w[i][y]);
            y=dp[i][y];
        }
    return min(ans,min(w[0][x],w[0][y]));
}
int main(){
    n=read(),m=read();
    memset(w,0x3f,sizeof(w));
    for(int i=1;i<=m;++i)
        a[i]={read(),read(),read()};
    kruskal();
    for(int i=1;i<=n;++i)
        if(!depth[i])
            dfs(i,0);
    int q=read();
    while(q--){
        int x=read(),y=read();
        printf("%d\n",lca(x,y));
    }
    return 0;
}