P1967 NOIP2013 提高组] 货车运输 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个题目算是lca的稍微拓展吧。主要思考方向应该是很明显的。就是考虑一条路径上权值最小的边。

1.首先这个题他不一定是联通图。其次我们发现是要在一个联通块内才能有有路径。还有题目不保证无环，所以我们要先建树。可以发现如果两个点之间有权值更大的路径是不会走权值小的路径的，比如题目中的例子。所以可以考虑建最大生成树。

void kruskal(){
    for(int i = 1; i <= n; i++){
        fa[i] = i;
    }
    sort(e + 1, e + 1 + m, [&](const edge &x, const edge &y){    
        return x.w > y.w;
    });
    for(int i = 1; i <= m; i++){
        auto [u, v, w] = e[i];
        int fau = find(u), fav = find(v);
        if(fau != fav){
            fa[fav] = fau;
            b[u].push_back({v, w});
            b[v].push_back({u, w});
        }
    }
}   

2.建好树之后如何思考呢？我们需要求一条路径上所有边权值的最小值，这个很好处理，就在lca的时候的再开一个数组记录以下就好。

for(int i = 1; i <= 20; i++){
    for(int j = 1; j <= n; j++){
        f[j][i] = f[f[j][i - 1]][i - 1];
        w[j][i] = min(w[j][i - 1], w[f[j][i - 1]][i - 1]);
    }
}

3.最后的查询就直接求两个点lca就行，求lca每次往上跳的时候求一下该段路径的最小值。注意两个点不在一个联通块的情况。

int lca(int x, int y){
    if(find(x) != find(y)) return -1;
    if(d[x] < d[y]) swap(x, y);
    int z = d[x] - d[y];
    int ans = inf;
    for(int j = 0; j <= 20 && z; j++, z /= 2){
        if(z & 1){
            ans = min(ans, w[x][j]);
            x = f[x][j];
        }
    }
    if(x == y){
        return x;
    }
    for(int i = 20; i >= 0; i--){
        if(f[x][i] != f[y][i]){
            ans = min({ans, w[x][i], w[y][i]});
            x = f[x][i];
            y = f[y][i];
        }
    }
    ans = min({ans, w[x][0], w[y][0]});
    return (ans == inf ? -1 : ans);
}

4.完整代码

#include<bits/stdc++.h>
using namespace std;
​
​
const int N = 5e4 + 100;
const int inf = 1 << 30;
struct edge{
    int u, v, w;
}e[N];
vector<pair<int,int>>b[N];
int fa[N];
int n, m;
int d[N], f[N][21], w[N][21];
bool st[N];
​
​
void kruskal();
int find(int);
int lca(int,int);
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
​
​
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {u ,v, w};
    }
    kruskal();
    function<void(int,int)> dfs = [&](int u, int fa){
        st[u] = true;
        d[u] = d[fa] + 1; 
        f[u][0] = fa;
        for(auto [v, b_w] : b[u]){
            if(st[v]) continue;
            w[v][0] = b_w;
            dfs(v, u);
        }
    };
    for(int i = 1; i <= n; i++){
        if(!st[i]){
            dfs(i, 0);
            w[i][0] = 1 << 30;
        }
    }
    for(int i = 1; i <= 20; i++){
        for(int j = 1; j <= n; j++){
            f[j][i] = f[f[j][i - 1]][i - 1];
            w[j][i] = min(w[j][i - 1], w[f[j][i - 1]][i - 1]);
        }
    }
    int q;
    cin >> q;
    while(q--){
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << '\n';
    }
    return 0;
}
void kruskal(){
    for(int i = 1; i <= n; i++){
        fa[i] = i;
    }
    sort(e + 1, e + 1 + m, [&](const edge &x, const edge &y){    
        return x.w > y.w;
    });
    for(int i = 1; i <= m; i++){
        auto [u, v, w] = e[i];
        int fau = find(u), fav = find(v);
        if(fau != fav){
            fa[fav] = fau;
            b[u].push_back({v, w});
            b[v].push_back({u, w});
        }
    }
}   
int find(int x){
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
int lca(int x, int y){
    if(find(x) != find(y)) return -1;
    if(d[x] < d[y]) swap(x, y);
    int z = d[x] - d[y];
    int ans = inf;
    for(int j = 0; j <= 20 && z; j++, z /= 2){
        if(z & 1){
            ans = min(ans, w[x][j]);
            x = f[x][j];
        }
    }
    if(x == y){
        return x;
    }
    for(int i = 20; i >= 0; i--){
        if(f[x][i] != f[y][i]){
            ans = min({ans, w[x][i], w[y][i]});
            x = f[x][i];
            y = f[y][i];
        }
    }
    ans = min({ans, w[x][0], w[y][0]});
    return (ans == inf ? -1 : ans);
}
/*
    核心任务求得就是一条路径的最小值
    可以先建立一颗最大生成树,显而易见就是两个点之间如果能通过大边联系时不会通过小边的
    然后再dp把 w[i][j] = min(w[i][j - 1], w[fa[i][j - 1]][j - 1]);
    最后lca就是求某一段路径上的w
*/