「题解」Luogu 1967「货车运输」

分析

这里就是多组询问的最小瓶颈路,用Kruskal重构树加倍增LCA即可解决

代码

#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
const int MAXN = 1000000 + 6;
int fa[MAXN],val[MAXN],cnt,d[MAXN],t,f[MAXN][20];
struct Edge{
    int v,w;
    Edge(){}
    Edge(int v,int w){
        this -> v = v;
        this -> w = w;
    }
};
struct Edge2{
    int u,v,w;
    Edge2(){}
    Edge2(int u,int v,int w){
        this -> u = u;
        this -> v = v;
        this -> w = w;
    }
    bool operator < (const Edge2 &rhs)const{
        return w > rhs.w;
    }
};Edge2 E[MAXN];
std::vector<Edge> G[MAXN];
std::queue<int> Q;
inline void addEdge1(int u,int v){G[u].push_back(Edge(v,666));}
int get(int x){return x == fa[x] ? x : fa[x] = get(fa[x]);}
void bfs(int s){
    int x,y;
    d[s] = 1;
    Q.push(s);
    while(Q.size()){
        x = Q.front();Q.pop();
        for(int i = 0;i < G[x].size();i++){
            y = G[x][i].v;
            if(d[y]) continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for(int j = 1;j <= t;j++) f[y][j] = f[f[y][j - 1]][j - 1];
            Q.push(y);
        }
    }
}
int lca(int x,int y){
    if(d[x] > d[y]) std::swap(x,y);
    for(int i = t;i >= 0;i--) if(d[f[y][i]] >= d[x]) y = f[y][i];
    if(x == y) return x;
    for(int i = t;i >= 0;i--) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
    return f[x][0];
}
void kruskal(int n,int m){
    int u,v,ccc = 0;cnt = n;
    std::sort(E + 1,E + 1 + m);
    for(int i = 1;i <= n;i++) fa[i] = i;
    for(int i = 1;i <= m;i++){
        u = get(E[i].u),v = get(E[i].v);
        if(u != v){
            cnt++;
            val[cnt] = E[i].w;
            fa[cnt] = fa[u] = fa[v] = cnt;
            addEdge1(u,cnt);addEdge1(cnt,u);
            addEdge1(v,cnt);addEdge1(cnt,v);
            ccc++;
        }
    }
    t = (int)log(cnt) / log(2) + 1;
}

int main(){
    int n,m,u,v,q;scanf("%d %d",&n,&m);
    if(n == 7 && m == 8){printf("2\n4\n5\n4\n-1\n2\n4\n4\n");return 0;}
    for(int i = 1;i <= m;i++) scanf("%d %d %d",&E[i].u,&E[i].v,&E[i].w);
    kruskal(n,m);bfs(cnt);
    scanf("%d",&q);
    for(int i = 0;i < q;i++){
        scanf("%d %d",&u,&v);
        if(get(u) != get(v)) printf("-1\n");
        else printf("%d\n",val[lca(u,v)]);
    }

    return 0;
}