洛谷题单<最小生成树> 货车运输

首先题目要求路径中的最大的最小值 所以建立最大生成图那么唯一路径中的最小值就是题目答案
又因为如果使用dfs/bfs求最小值的话 时间复杂度是 O(n * q) 会超时 所以使用lca（最近公共祖先）的思路求路径最小值。不了解的话建议在ACwing 上y总在提高课中有讲到（安利一波）或者阅读：https://blog.csdn.net/jeryjeryjery/article/details/52853017
我们在裸的模板 上还要在维护 wmin 数组 （wmin[a][i] 表示a点向上找2^i个祖先的最短边）
建议lca建树的dfs 写成bfs 因为dfs有爆栈的风险。
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 10010, M = 50010;

struct edge{
    int a, b, c;
    bool operator<(const edge& t)const{
        return c > t.c;
    }
}edges[M];

int h[N], e[M], ne[M], w[M], idx; //邻接表存最大生成树 
int p[N], father[N][25], wmin[N][25], depth[N];//邻接表 ；lca 倍增求法
int n, m, st[N];
int find(int x){
    if(x == p[x]) return x;
    else return p[x] = find(p[x]);
} 
void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

void kruskal(){
    sort(edges, edges + m);
    for(int i = 0; i <= n; i++) p[i] = i;

    for(int i = 0; i < m; i ++){
        int a = edges[i].a, b = edges[i].b, c = edges[i].c;
        int x = find(a), y = find(b);
        if(x != y){
            p[x] = y;
            add(a, b, c);
            add(b, a, c);
        }
    }
}

void bfs(int k){
    st[k] = 1;
    queue<int> q;
    q.push(k);
    while(q.size()){
        int son = q.front(); q.pop();
        for(int i = h[son]; i != -1; i = ne[i]){
            int j = e[i];
            if(!st[j]){
                q.push(j);
                st[j] = 1;
                depth[j] = depth[son] + 1;
                father[j][0] = son;
                wmin[j][0] = w[i];
                for(int i = 1; i <= 20; i++){
                    father[j][i] = father[father[j][i-1]][i-1];
                    wmin[j][i] = min(wmin[j][i-1], wmin[father[j][i-1]][i-1]);//更新father 和 wmin 数组；
                }
            }
        }
    }
}

int lca(int a, int b){
    int ans = 0x3f3f3f3f;
    if(find(a) != find(b)) return -1;
    if(depth[a] < depth[b]) swap(a, b);
    for(int i = 20; i >= 0; i--){
        if(depth[father[a][i]] >= depth[b]){
            ans = min(ans, wmin[a][i]);
            a = father[a][i];
        }
    }
    if(a == b) return ans;
    for(int i = 20; i >= 0; i--){
        if(father[a][i] != father[b][i]){
            ans = min(ans, min(wmin[a][i], wmin[b][i]));
            a = father[a][i];
            b = father[b][i];
        }
    }
    ans = min(ans, min(wmin[a][0], wmin[b][0]));
    return ans;
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h); 
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }
    kruskal();
    for(int i = 1; i <= n; i++){
        if(!st[i]){
            depth[i] = 1;
            bfs(i);
        }
    }
    int query;
    cin >> query;
    while(query --){
        int a, b;
        scanf("%d%d", &a, &b);
        int ans = lca(a, b);
        printf("%d\n", ans);
    }

    return 0;
}