题目传送门

题目分析

刚看到这个题目怎么也无法把它跟生成树联系到一起,直到后来看懂题是在求一条瓶颈路。
既然是两个点之间最小的边最大,那么很显然就是一条瓶颈路,求一条瓶颈路的方法有很多,有人应该会想到二分答案,这种方法是可行的,但是由于这道题是多次询问,时间难以承受,所以就要用生成树。上面博客已经介绍过这种方法,这里就不再赘述。由于是让路径上的最小边最大,所以应该拍一棵最大生成树,题中说的两点之间多条边也就对我们没什么影响。当生成一颗棵最大生成树后,任意两点之间的瓶颈路就是书上所保留下来的边组成的路,紧接着我们用倍增维护一下人任意点的祖先以及到该祖先路上的最小权值。然后就可以用LCA轻而易举的求出任意两点之间瓶颈路上的最小权值。对于输出$-1$的情况,一定是两个点不连通,可以用并查集来维护,然后这道题就可以AC啦！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
# include <algorithm>
# include <cstring>
# include <iostream>
# include <cstdio>
# include <cmath>
# include <queue>
# define R register
# define LL long long

using namespace std;

struct pp {int v,u,w;} ed[50010];
struct bb {int v,w,pre;} edge[100010];
int f[10010][21],d[10010][21],dep[10010],fa[10010],h[10010],e,n,m,q;

inline void maxx(int &a,const int &b){a>b? :a=b;}

inline void in(R int &a){
    R int c = getchar();R int x = 0,f = 1;
    while(!isdigit(c)){if(c == '-')f=-1; c = getchar();}
    while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
    a = x*f;
}

inline void add(R int x,R int y,R int w){
    edge[++e] = (bb){y,w,h[x]};
    h[x] = e;
}

inline void minn(R int &x,const int y,const int z){x= y<z? y:z;}

inline bool cmp(pp a,pp b){return a.w>b.w;}

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

inline void dfs(R int x){

    for(R int i=0; f[f[x][i]][i]; ++i)  f[x][i+1] = f[f[x][i]][i],minn(d[x][i+1],d[x][i],d[f[x][i]][i]);

    for(R int i=h[x]; i; i=edge[i].pre)
    {
        if(dep[edge[i].v]) continue;
        f[edge[i].v][0] = x;
        d[edge[i].v][0] = edge[i].w;
        dep[edge[i].v] = dep[x]+1;
        dfs(edge[i].v);
    }
}

inline int lca(R int x,R int y){
    R int ans = 2147483647;
    if(dep[x]<dep[y]) x^=y,y^=x,x^=y;
    R int t = log2(dep[x]-dep[y])+1;
    for(R int i=t; i>=0; --i) if(dep[f[x][i]] >= dep[y]) minn(ans,ans,d[x][i]),x = f[x][i];
    if(x == y) return ans;
    t = log2(dep[x])+1;
    for(R int i=t; i>=0; --i)
    {

        if(f[x][i] == f[y][i]) continue;
        R int tot;
        minn(tot,d[x][i],d[y][i]);
        x=f[x][i],y=f[y][i];
        minn(ans,ans,tot);
    }
    R int tot;
    minn(tot,d[x][0],d[y][0]);
    minn(ans,ans,tot);
    return ans;
}

inline int yg(){
    freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);
    in(n),in(m);
    R int x,y,z;
    for(R int i=1; i<=n; ++i) fa[i] = i;
    for(R int i=1; i<=m; ++i)
    {
        in(x),in(y),in(z);
        ed[i]=(pp){x,y,z};
    }
    sort(ed+1,ed+m+1,cmp);
    for(R int i=1; i<=m; ++i)
    {
        R int p=find(ed[i].u),q=find(ed[i].v);
        if(p!=q) add(ed[i].u,ed[i].v,ed[i].w),add(ed[i].v,ed[i].u,ed[i].w),fa[p] = q;
    }
    dep[1] = 1;
    dfs(1);
    in(q);
    for(R int i=1; i<=q; ++i)
    {
        in(x),in(y);
        if(find(x)!=find(y)) {printf("-1\n");continue;}
        printf("%d\n",lca(x,y));
    }
}

int youngsc = yg();
int main(){;}