原题大意

qwb打算向学姐表白，可是学姐已经受够了他的骚扰，于是出了一个题想难住他:已知一幅n个点m条边的无向图,定义 路径的值为这条路径上最短的边的长度，现在有k个询问，询问从A点到B点的所有路径的值的最大值。

算法分析

题目意思是查询图上两点的瓶颈路大小，这个训练指南上有讲解。
先是求最大生成树，然后求树上两点路径的最小值，用LCA倍增法就可以了。

http://blog.csdn.net/Janis_z/article/details/52937631?locationNum=6&fps=1

程序代码

template <class T> inline void umin(T &a,T b){a=min(a,b);}
template <class T> inline void umax(T &a,T b){a=max(a,b);}
const int N=50005;
struct Bian{  
    int u;    
    int v;
    int w;
};
int p[N],ra[N]; 
Bian  bian[200005];
vector<pii> G[N];
bool cmp(const Bian &p1,const Bian &p2){
    return p1.w>p2.w;
}
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
int Union(int x,int y) {
    x=find(x);
    y=find(y);
    if(x==y)return 0;
    if(ra[x]>ra[y]) {
        p[y]=x;
    }else{
        if(ra[x]==ra[y])ra[y]++;
        p[x]=y;
    }
    return 1;
}
void Kruskal(int kn,int km){
    for(int i=1;i<=kn;i++){
         p[i]=i;   
    }
    sort(bian,bian+km,cmp);
    for(int i=0;i<km;i++){
        if(Union(bian[i].u,bian[i].v)){
            G[bian[i].u].push_back({bian[i].v,bian[i].w});
            G[bian[i].v].push_back({bian[i].u,bian[i].w});
        }
    }
}



int d[N][20],f[N][20];
int dep[N];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i].ff;
        if(v==fa)continue;
        f[v][0]=u;
        d[v][0]=G[u][i].ss;
        dfs(v,u);
    }
}
int main() {
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&bian[i].u,&bian[i].v,&bian[i].w);
    }
    Kruskal(n,m);
    dep[1]=1;
    dfs(1,0);
    int wc=0;//log深度 
    for(int i=1;;wc++){
        i<<=1;
        if(i>n)break;
    } 
    for(int j=1;j<=wc;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
            d[i][j]=min(d[i][j-1],d[f[i][j-1]][j-1]);
        }
    }
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        int ans=INF;
        if(dep[x]<dep[y])swap(x,y);
        for(int i=wc;i>=0;i--){
            if(dep[f[x][i]]>=dep[y]){
                umin(ans,d[x][i]);
                x=f[x][i];
                if(dep[x]==dep[y])break;
            }
        }
        //如果xy不在同一侧
        if(x!=y){
            for(int i=wc;i>=0;i--){
                if(f[x][i]!=f[y][i]){
                    umin(ans,d[x][i]);
                    umin(ans,d[y][i]);
                    x=f[x][i];
                    y=f[y][i];
                } 
            }
            //到0倍父亲
            umin(ans,d[x][0]);
            umin(ans,d[y][0]);
        }
        printf("%d\n",ans);
    }
    return 0;
}