P1967 货车运输

题面:https://www.luogu.org/problemnew/show/P1967

本题是一个Kruskal重构树应用—求图中任意两点间所有路径中最小边权的最大值。
在kruskal的过程中，若当前边所连两点u和v不在一个集合内，则新建一个节点node，点权为该边边权，然后连接u所在集合的根与node以及v所在集合的根与node，重构完成之后，指定每个集合的根作为所在森林的根，则u到v路径上最大边权的最小值(这里的kruskal要做成最大生成树)，就是LCA(u,v)的点权。

Code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=200005;
int n,m,cnt;
struct node{
    int u,v,dis;
}edge[N];
bool cmp(node a,node b){
    return a.dis>b.dis;
}
struct node2{
    int v,Next;
}E[N];
int head[N],tot,val[N],root[N],vis[N],father[N],top[N],son[N],size[N],dep[N],q;
void add(int u,int v){
    E[++tot].Next=head[u];
    E[tot].v=v;
    head[u]=tot;
}
int find(int x){
    if(x==root[x]){
        return x;
    }
    else {
        return root[x]=find(root[x]);
    }
}
void dfs1(int u,int fa){
    size[u]=1;
    vis[u]=1;
    for(int i=head[u];i;i=E[i].Next){
        int v=E[i].v;
        if(v==fa){
            continue;
        }
        dep[v]=dep[u]+1;
        father[v]=u;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[v]>size[son[u]]){
            son[u]=v;
        }
    }
}
void dfs2(int u,int fa){
    top[u]=fa;
    if(son[u]){
        dfs2(son[u],fa);
    }
    for(int i=head[u];i;i=E[i].Next){
        int v=E[i].v;
        if(v==father[u]||v==son[u]){
            continue;
        }
        dfs2(v,v);
    }
}
void kruskal(){
    sort(edge+1,edge+1+m,cmp);
    for(int i=1;i<=n;i++){
        root[i]=i;
    }
    for(int i=1;i<=m;i++){
        int fu=find(edge[i].u),fv=find(edge[i].v);
        if(fu!=fv){
            val[++cnt]=edge[i].dis;
            root[cnt]=root[fu]=root[fv]=cnt;
            add(fu,cnt);
            add(cnt,fu);
            add(fv,cnt);
            add(cnt,fv);
        }
    }
    for(int i=1;i<=cnt;i++)
    if(!vis[i])
    {
        int f=find(i);
        dfs1(f,0);
        dfs2(f,f);
    }
}
int LCA(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]){
            u=father[top[u]];
        }
        else{
            v=father[top[v]];
        }
    }
    return dep[u]<dep[v]?u:v;
}
int main(){
    cin>>n>>m;
    cnt=n;
    for(int i=1;i<=m;i++){
        cin>>edge[i].u>>edge[i].v>>edge[i].dis;
    }
    kruskal();
    cin>>q;
    while(q--){
        int u,v;
        cin>>u>>v;
        if(find(u)!=find(v)){
            cout<<"-1"<<endl;
        }
        else{
            cout<<val[LCA(u,v)]<<endl;
        }
    }
    return 0;
}

P1967 货车运输

原文：https://www.cnblogs.com/ukcxrtjr/p/11186320.html