luogu1967 貨車運輸

似乎是什麼最大瓶頸路徑（顧名思義），它存在于最大生成樹中。

證明：

如果最大瓶頸路徑不存在與最大生成樹中。

這些不在最大生成樹中的邊會和最大生成樹形成環。

我們删掉環上最小的邊，保留這一條邊，會得到一棵新的更大的生成樹。

這與原來那棵樹是最大生成樹沖突了。

注意，最短路不一定在最小生成樹上（如一個環的情況）

摘自洛谷題解。作者crf1596028912，摘自高天宇學長SD夏令營的PPT

我們用和倍增lca差不多的方法求之。

這代碼賊長。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, m, grand[][], minq[][], fa[], hea[], cnt;
int r1, r2, deep[], q, uu, vv;
struct Ed{
    int fro, too, val;
}ed[];
struct Edge{
    int too, nxt, val;
}edge[];
int rn(int &x){
    char ch=getchar();
    x = ;
    while(ch<'0' || ch>'9') ch = getchar();
    while(ch>='0' && ch<='9'){
        x = x* + ch - '0';
        ch = getchar();
    }
    return x;
}
void init(){
    rn(n);
    rn(m);
    for(int i=; i<=m; i++){
        rn(ed[i].fro);
        rn(ed[i].too);
        rn(ed[i].val);
    }
    for(int i=; i<=n; i++)
        fa[i] = i;
}
bool cmp(Ed x, Ed y){
    return x.val>y.val;
}
int myfind(int x){
    return fa[x]==x?x:fa[x]=myfind(fa[x]);
}
void add_edge(int fro, int too, int val){
    edge[++cnt].too = too;
    edge[cnt].nxt = hea[fro];
    edge[cnt].val = val;
    hea[fro] = cnt;
}
void kruskal(){
    sort(ed+, ed++m, cmp);
    int ecnt=;
    for(int i=; i<=m; i++){
        r1 = myfind(ed[i].fro);
        r2 = myfind(ed[i].too);
        if(r1!=r2){
            fa[r2] = r1;
            add_edge(ed[i].fro, ed[i].too, ed[i].val);
            add_edge(ed[i].too, ed[i].fro, ed[i].val);
        }
    }
}
void bd(int u){
    for(int i=hea[u]; i; i=edge[i].nxt){
        int t=edge[i].too;
        if(!deep[t]){
            grand[t][] = u;
            minq[t][] = edge[i].val;
            deep[t] = deep[u] + ;
            bd(t);
        }
    }
}
void inits(){
    for(int i=; i<=; i++)
        for(int j=; j<=n; j++){
            grand[j][i] = grand[grand[j][i-]][i-];
            minq[j][i] = min(minq[j][i-], minq[grand[j][i-]][i-]);
        }
}
int lca(int x, int y){
    int ans = ;
    if(deep[x]<deep[y]){
        x ^= y;
        y ^= x;
        x ^= y;
    }
    for(int i=; i>=; i--)
        if(deep[grand[x][i]]>=deep[y]){
            ans = min(ans, minq[x][i]);
            x = grand[x][i];//請注意語句次序！！！
        }
    if(x==y)    return ans;
    for(int i=; i>=; i--)
        if(grand[x][i]!=grand[y][i]){
            ans = min(ans, min(minq[x][i], minq[y][i]));
            x = grand[x][i];
            y = grand[y][i];//請注意語句次序！！！
        }
    return min(ans, min(minq[x][], minq[y][]));
}
int main(){
    init();
    kruskal();
    for(int i=; i<=n; i++)
        if(!deep[i]){
            deep[i] = ;
            bd(i);
        }
    inits();
    rn(q);
    for(int i=; i<=q; i++){
        rn(uu);
        rn(vv);
        if(myfind(uu)!=myfind(vv))  printf("-1\n");
        else                        printf("%d\n", lca(uu, vv));
    }
    return ;
}