题目链接

<h1>题目大意</h1>

给出一个由 $ n $个点 $ m $条边的图，现有$ q $组询问，每次需要你求出从$ x $到$ y $的一条简单路径，使路径上所有边中最小值最大，并输出这个最大值。

若不存在这样的路径，则输出$ −1 $。

<h1>解题报告</h1>

做这一道题之前，建议先看一下单次询问的最长瓶颈路这道题目。

注意解法二：我们最后的答案其实就在最小生成树上。

即我们可以证明：无向图中最小生成树中u到v的路径一定是u到v的最小瓶颈路之一。

同理：无向图中最大生成树中u到v的路径一定是u到v的最大瓶颈路之一。

所以说，对于这一道题，我们对这个无向图预先进行求最大生成树，然后这道题就成功的转化为求u到v的路径上的最小值。我们可以用LCA解决。

具体来说是我们在对f数组进行预处理时，维护一个从该节点向上跳2^k的父亲中经过的所有边的最小值。

查询？只需要在同时跳 $ u $ 和 $v$ 的时候，顺便更新最小值即可。个人感觉思想类似于树链剖分中的查询操作。

<h1>样例代码</h1>

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using std::min;
using std::sort;
const int MAXN = 100000 + 5;

int N,M,Q;
float log2N;

struct Graph{
    int u,v,w;

    bool operator < (const Graph &other) const{
        return w > other.w;
    }
}e[MAXN * 2];

struct Node{
    int num,depth;
    bool used;
    struct Edge *firstEdge;
}node[MAXN];

struct Edge{
    Node s,t;
    int w;
    Edge *next;
}pool[MAXN  2],frog = pool;

Edge New(Node s,Node *t,int w){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->w = w;ret->next = s->firstEdge;
    return ret;
}

inline void add(int u,int v,int w){
    node[u].firstEdge = New(&node[u],&node[v],w);
    node[v].firstEdge = New(&node[v],&node[u],w);
}

int fa[MAXN];

int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void Kruskal(){
    for(int i = 1;i <= N;i++)
        fa[i] = i;
    sort(e + 1,e + M + 1);
    int cnt = 0;
    for(int i = 1;i <= M;i++){
        int fx = find(e[i].u),fy = find(e[i].v);
        if(fx == fy) continue;
        add(e[i].u,e[i].v,e[i].w);
        fa[fy] = fx;
        if(++cnt == N - 1) break;
    }
}

int fMAXN,maxvMAXN;

inline void init(){
    for(int i = 1;i <= N;i++){
        node[i].depth = 0;
        node[i].num = i;
        node[i].used = false;
    }
    log2N = log(N)/log(2);
}

void dfs(Node *v){
    for(int i = 1;i <= log2N;i++){
        if(v->depth <= (1<<i)) break;
        fv->num = ff[v->num][i-1];
        maxvv->num = min(maxvv->num,maxvf[v->num][i-1]);
    }
    for(Edge *e = v->firstEdge;e;e = e->next){
        if(!e->t->used){
            e->t->used = true;
            e->t->depth = v->depth + 1;
            maxve->t->num = e->w;
            fe->t->num = v->num;
            dfs(e->t);
        }
    }
}

int query(int u,int v){
    if(find(u) != find(v)) return -1;
    int ret = INT_MAX;
    if(node[u].depth < node[v].depth)
        std::swap(u,v);
    for(int j = log2N;j >= 0;j--){
        if(node[u].depth - (1<<j) >= node[v].depth){
            ret = min(ret,maxvu); 
            u = fu;
        }
    }
    if(u == v) return ret;
    for(int j = log2N;j >= 0;j--){
        if(fu && fu != fv){
            ret = min(ret,min(maxvu,maxvv));
            u = fu;
            v = fv;
        }
    }
    return min(ret,min(maxvu,maxvv));
}

int main(){
    memset(f,-1,sizeof(-1));
    scanf("%d%d",&N,&M);
    for(int i = 1;i <= M;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    Kruskal();
    init();
    dfs(&node[(1 + N) >> 1]);
    scanf("%d",&Q);
    while(Q--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%dn",query(x,y));
    }
    return 0;
}