$qn$

每辆货车的最大载重，等价于找到最大的一条从$x$走到$y$的路线,那这样可以启发我们使用并查集从大到小依次加入每条边，那么第一次加入的使得$x,y$连通的边就是我们要求的答案.

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=50010;
int p[N];
struct Edge{ //按照边权重大到小排序
    int a,b,w;
    bool operator<(const Edge& E)const
    {
        return w>E.w;
    }
}e[M];
int find(int x) //并查集模板
{
    if(x!=p[x])
    {
        p[x]=find(p[x]);
    }
    return p[x];
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].a>>e[i].b>>e[i].w;   
    }
    sort(e+1,e+m+1);
    int q;
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        for(int i=1;i<=n;i++)
        {
            p[i]=i;
        }
        int res=-1;
        for(int i=1;i<=m;i++)
        {
            int pa=find(e[i].a),pb=find(e[i].b);
            if(pa!=pb)
            {
                p[pa]=pb;
            }
            if(p[find(x)]==p[find(y)]) //加入了第i条边以后x和y连通,之前x,y没有连通
            {
                res=e[i].w;
                break;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

$qlogn$

我们发现每次查询的时候需要枚举所有边去构造最大生成树,其实我们可以先构造完整的最大生成树,然后使用倍增的方式去找到$x$到$y$的这条路径上的最最小的边权是什么。

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=50010,K=14,INF=1e8;
int h[N],e[N*2],w[N*2],ne[N*2],idx;
int fa[N][K],dep[N],g[N][K]; //倍增数组
//fa[x][k] 表示x往上跳2^k步的位置,g[x][k]表示往上跳2^k的最小值
int p[N];
int n,m;
struct Edge{
    int a,b,c;
    bool operator<(const Edge& W)const
    {
        return c>W.c;
    }
}edge[M];
int find(int x) //并查集模型
{
    if(p[x]!=x)
    {
        p[x]=find(p[x]);
    }
    return p[x];
}
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs(int u,int father,int depth) //深度优先搜索处理倍增数组
{
    dep[u]=depth; //当前点的深度
    for(int i=h[u];i!=-1;i=ne[i]) //枚举所有子节点
    {
        int j=e[i];
        if(j==father) continue;
        fa[j][0]=u,g[j][0]=w[i]; //只走一步
        for(int k=1;k<K;k++) //递推计算其它步
        {
            g[j][k]=min(g[j][k-1],g[fa[j][k-1]][k-1]);
            fa[j][k]=fa[fa[j][k-1]][k-1];
        }
        dfs(j,u,depth+1); //继续搜索下面层
    }
}
int lca(int a,int b) //寻找公共祖先
{
    if(find(a)!=find(b)) return -1; //保证a和b在同一个书
    if(dep[a]<dep[b]) swap(a,b); //保证a的深度大于等于b的深度
    int res=INF;
    for(int k=K-1;k>=0;k--) //a跳到和b同一层
    {
        if(dep[fa[a][k]]>=dep[b])
        {
            res=min(res,g[a][k]);
            a=fa[a][k];   
        }
    }
    if(a==b) return res; //跳到同一层
    for(int k=K-1;k>=0;k--) //跳到公共祖先的下一层
    {
        if(fa[a][k]!=fa[b][k])
        {
            res=min(res,min(g[a][k],g[b][k]));
            a=fa[a][k],b=fa[b][k];
        }
    }
    res=min(res,min(g[a][0],g[b][0])); //跳到公共祖先
    return res;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) //所有边
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i]={a,b,c};
    }
    sort(edge+1,edge+1+m); //按照边排序
    for(int i=1;i<=n;i++) //并查集初始化
    {
        p[i]=i;
    }
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++) //构建最大生成树
    {
        int a=edge[i].a,b=edge[i].b,c=edge[i].c;
        if(find(a)!=find(b))
        {
            p[find(a)]=find(b);
            add(a,b,c);
            add(b,a,c);
        }
    }
    for(int i=1;i<=n;i++) //处理每颗树
    {
        if(dep[i]==0)
        {
            dfs(i,-1,1);
        }
    }
    int q;
    cin>>q;
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
    return 0;
}