传送门

算法：最大生成树 & LCA

题目要求两点之间最小边权的最大值..

就是两点之间有多条路径，每条路径有一个最小边权

要找到最大的最小边权

考虑kruskal算法的过程

如果我们每次把能使图两个块联通的最大的边加入图中

那么最终出来的图就称为最大生成树

显然在最大生成树中，两点之间的路径一定是题目要求的最小边权最大的路径

因为如果有更优的一条路可以替代原本的路，那么在之前求最大生成树的过程中就会被选择

好吧可能不太清楚，换个说法：

在kruskal过程时

假设已经选了几条边

现在我们要找一条边能使其中两个块联通

联通完后车就可以从一个块走到另一个块

那么我们要找哪条边呢

显然是最大的边

如果选比较小的边

那还不如选更大的边，还可以尽量增加车的最大载重

对于任意的块都显然成立

所以要建最大生成树

建完了然后就是处理询问

不能直接暴力，询问太多

想想要怎么快速处理出树上两点间的询问呢

我会树链剖分！

为什么要这么麻烦

考虑LCA的思想..

就这样搞：

设mi[ i ][ j ] 为从节点 i 往上2^j 段路径的最小值

然后LCA怎么搞就怎么搞了

顺便注意一下可能图不联通...

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
struct edge
{
    int a,b,v;
}e[50005];//原来的边
int n,m,q,fa[10005],f[10005][21],dep[10005],mi[10005][21];
struct Edge
{
    vector <int> v,dis;//vector用起来多方便啊
}ev[10001];//最大生成树的边
bool p[10005];
bool cmp(const edge a,const edge b){return a.v>b.v; }
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}//搞kruskal当然要并查集，而且顺便可以判断两点是否联通（原图可能不联通）
void dfs(int x,int father)//预处理mi
{
    dep[x]=dep[father]+1;f[x][0]=father;
    for(int i=1;i<=20;i++)
    {
        f[x][i]=f[f[x][i-1]][i-1];
        mi[x][i]=min(mi[f[x][i-1]][i-1],mi[x][i-1]);
    }
    int len=ev[x].v.size();
    for(int i=0;i<len;i++)
    {
        int u=ev[x].v[i];
        if(u==father) continue;
        mi[u][0]=ev[x].dis[i];
        dfs(u,x);
    }
}
int lca(int x,int y)//求两点间路径上最短的边
{
    int res=99999999;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[f[x][i]]>=dep[y])
        { 
            res=min(res,mi[x][i]);
            x=f[x][i];
        }
    if(x==y) return res;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
        {
            res=min(res,min(mi[x][i],mi[y][i]));
            x=f[x][i];
            y=f[y][i];
        }
    return min(res,min(mi[x][0],mi[y][0]));
}
int main()
{
    memset(mi,0x7f,sizeof(mi));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int xa=find(e[i].a),xb=find(e[i].b);
        if(xa==xb) continue;
        fa[xa]=xb;
        ev[e[i].a].v.push_back(e[i].b);
        ev[e[i].b].v.push_back(e[i].a);
        ev[e[i].a].dis.push_back(e[i].v);
        ev[e[i].b].dis.push_back(e[i].v);
    }//kruskal算法
    for(int i=1;i<=n;i++)//原图可能不联通，要把每个点找一遍
    {
        int xa=find(i);
        if(p[xa]) continue;
        p[xa]=1;
        dfs(xa,xa);
    }
    cin>>q;
    int a,b;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&a,&b);
        int xa=find(a),xb=find(b);
        if(xa!=xb)
        {
            cout<<"-1"<<endl;
            continue;
        }
        cout<<lca(a,b)<<endl;
    }//处理询问
    return 0;
}

P1967 货车运输

传送门

推荐阅读