浅析最小瓶颈路问题

最小瓶颈路问题是指在一张无向图中，询问点对$(u,v)$，需要找出从$u$到$v$的一条简单路径，使路径上所有边中最大值最小。

对于这类问题我们有两种做法，一是利用最小生成树的性质，二是利用$Kruskal$重构树的性质

壹

首先我们要知道的一点是：

无向图最小生成树中$u$到$v$的路径一定是$u$到$v$的最小瓶颈路之一（因为最小瓶颈路很可能有多条）

我们知道了这个性质之后，对于多组查询我们有如下思路：

先用$kruskal$算法构建一颗最小生成树$(MST)$，接下来用$DFS$把最小生成树转化成有根树。然后就变成了对于每个询问$(u,v)$，回答$u$到$v$的路径上的权值最大值。这个可以用倍增$LCA$解决。

具体思路是在$ST$表预处理时，维护一个从该节点到其$k$级父亲中经过的所有边的最大权值。在查询中仍然将$u$和$v$往上跳，同时维护路径中最大值，到其$LCA$结束。（也可以在$DFS$的时候处理，就和倍增$LCA$的两种写法是一样的）

下面上道LOJ上小瓶颈路的裸题：最小瓶颈路

首先根据$kruskal$算法得出最小生成树，由于这里的根节点不确定，所以我们读入的是双向边

void kruskal(){
    for(int i = 1; i <= n; i++) fa[i] = i;
    sort(edge + 1, edge + 1 + m, cmp);
    int times = 1;
    for (int i = 1; i <= m&&times <= n-1; i++) {
        int fx=find(edge[i].u), fy=find(edge[i].v);
        if(fx!=fy){
            fa[fx] = fy, times++;
            add(edge[i].u, edge[i].v, edge[i].w);
            add(edge[i].v, edge[i].u, edge[i].w);
        }  
    }
}

接着我们把这颗无根树通过$DFS$转化成有根树，方便我们后面$LCA$的求解

void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v==fa) continue;
        f[v][0] = u, maxw[v][0] = e[i].w;
        dfs(v, u);
    }
}

也可以这么写，我个人偏向于第二种

void dfs(int u){
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v==f[u][0]) continue;
        f[v][0] = u, maxw[v][0] = e[i].w;
        dep[v] = dep[u]+1, dfs(v);
    }
}

最后就是在求解$LCA$的过程中得出最大边权值了

仔细看代码应该会体会更深：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
struct Edge{
    int next, to, w;
}e[maxn<<1];
struct node{
    int u, v, w;
}edge[maxn<<1];
bool cmp(node x, node y){ 
    return x.w < y.w; 
}
int n, m, k, cnt;
int head[maxn], dep[maxn], f[maxn][20], maxw[maxn][20], fa[maxn];
void add(int u, int v, int w){
    e[++cnt].next = head[u];
    e[cnt].to = v;
    e[cnt].w = w;
    head[u] = cnt;
}
int find(int x){ 
    return x==fa[x] ? fa[x] : fa[x]=find(fa[x]); 
}
void kruskal(){
    for(int i = 1; i <= n; i++) fa[i] = i;
    sort(edge + 1, edge + 1 + m, cmp);
    int times = 1;
    for (int i = 1; i <= m&&times <= n-1; i++) {
        int fx=find(edge[i].u), fy=find(edge[i].v);
        if(fx!=fy){
            fa[fx] = fy, times++;
            add(edge[i].u, edge[i].v, edge[i].w);
            add(edge[i].v, edge[i].u, edge[i].w);
        }  
    }
}
//将无根树转化成有根树
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v==fa) continue;
        f[v][0] = u, maxw[v][0] = e[i].w;
        dfs(v, u);
    }
}
/*
void dfs(int u){
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v==f[u][0]) continue;
        f[v][0] = u, maxw[v][0] = e[i].w;
        dep[v] = dep[u]+1, dfs(v);
    }
}
*/
int query(int x, int y) {
    if(dep[x]<dep[y]) swap(x, y);
    int t = (int)(log(dep[x]) / log(2)), res = 0;
    for (int i = t; i >= 0; i--) {
        if (dep[f[x][i]] >= dep[y]) {
            res = max(res, maxw[x][i]);
            x = f[x][i];
        }
        if(x==y) return res;
    }
    for (int i = t; i >= 0; i--) {
        if (f[x][i] && f[x][i] != f[y][i]) {
            res = max(res, max(maxw[x][i], maxw[y][i]));
            x = f[x][i];
            y = f[y][i];
        }
    }
    return max(res, max(maxw[x][0], maxw[y][0]));
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= m; i++)
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    kruskal();
    for(int i = 1; i <= n; i++){ //预处理lca,注意原图可能不联通,所以我们可能构出了一个森林 
        if (!dep[i]) dfs(i, 0);
        //这里dfs里面是i,0是因为根节点没有父亲
        //之前我在这里的理解存在误区, f[x][0]表示的是x的父节点, 而并查集中fa[x]表示x所在集合的代表, 不要混淆两者 
    }
    for (int j = 1; (1 << j) <= n; j++){
        for (int i = 1; i <= n; i++){
            //if(f[i][j - 1])的判断可有可无 
                f[i][j] = f[f[i][j - 1]][j - 1];
                maxw[i][j] = max(maxw[i][j - 1], maxw[f[i][j - 1]][j - 1]);
            
        }
    }
    while(k--){
        int s, t;
        scanf("%d%d", &s, &t);
        if (find(s)!=find(t)) puts("-1");
        else printf("%d
", query(s, t));
    }
    return 0;
}

View Code

贰

$Kruskal$生成树的解法参考这篇：Kruskal重构树

应用

由于最小瓶颈路不唯一，一般情况下会询问最小瓶颈路上的最大边权。

也就是说，我们只需要求最小生成树链上的 max就可以了

最小生成树的思路参考自：

https://www.cnblogs.com/XSC637/p/7663056.html

https://www.cnblogs.com/xiaoK-778697828/p/9665205.html

https://loj.ac/submission/630088

https://blog.csdn.net/Anxdada/article/details/80420071

https://www.cnblogs.com/konjak/p/6020958.html

https://blog.csdn.net/Originum/article/details/82258450（读入边）