UVA 11354 Bond ( 最小瓶頸路徑 Kruskal + LCA )

UVa Online Judge
題目是很裸的最小瓶頸路徑，一般的做法是 O( n * n )
生成樹相關問題 -- 訓練指南 - 0w1
但這題 n ≤ 50000，行不通，這時候就要使用比較難寫的最小瓶頸路徑，先進行一些預處理降到 O( n lg n ) 級別。注意求最小瓶頸路徑時我們用的 maxcost二維陣列，其實是一種 RMQ，令 cost( v )為 v 與其父節點連結的邊權，那麼 maxcost[ a ][ b ] 其實就等價於
max{ max{ cost( p ) | Ɐ p ∈ shortestPath[ a, lca( a, b ) ) }, max{ cost( q ) | Ɐ q ∈ shortestPath[ b, lca( a, b ) ) } }
於是我們發現 maxcost陣列可以在計算 LCA時一併處理，利用 doubling的算法解決。
小小領悟：像這樣好幾個算法一起用會亂，所以開個 struct把獨有的變數包進來會比較不礙手礙腳。全域變數盡量只留輸入的就可以了。
碎念：又是一題可樹鏈剖分，想早點學啊。。
uva 11354 - Bond(树链剖分) - 不慌不忙、不急不躁 - 博客频道 - CSDN.NET

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXLGN = 20;
const int INF = 1e9;

int kase;
int n, m, q;
struct Edge{
    int u, v, c;
    bool operator < (const Edge &oth){
        return c < oth.c;
    }
} es[MAXM];
vector<Edge> G[MAXN];

struct UnionFind{
    int fa[MAXN];
    void init(int n){ for(int i = 0; i <= n; ++i) fa[i] = i; }
    int find(int x){ return fa[x] == x ? x : fa[x] = find( fa[x] ); }
    bool unite(int a, int b){
        int x = find( a ), y = find( b );
        if( x == y ) return false;
        fa[ x ] = y; return true;
    }
} uf;

struct Kruskal{
    void solve(){
        sort( es, es + m );
        uf.init( n );
        for(int i = 1; i <= n; ++i) G[i].clear();
        for(int i = 0; i < m; ++i){
            int u = es[i].u, v = es[i].v, c = es[i].c;
            if( uf.unite( u, v ) ){
                G[ u ].push_back( (Edge){ u, v, c } );
                G[ v ].push_back( (Edge){ v, u, c } );
            }
        }
    }
} mst;

struct LCA{
    int depth[MAXN], fa[MAXN], cost[MAXN];
    int anc[MAXLGN][MAXN], maxcost[MAXLGN][MAXN];
    void preprocess(){
        memset( anc, -1, sizeof(anc) );
        memset( maxcost, -1, sizeof(maxcost) );
        for(int u = 1; u <= n; ++u){
            anc[0][u] = fa[u];
            maxcost[0][u] = cost[u];
        }
        for(int i = 1; ( 1 << i ) <= n; ++i)
            for(int u = 1; u <= n; ++u)
                if( anc[i - 1][u] != -1 ){
                    int k = anc[i - 1][u];
                    if( anc[i - 1][k] == -1 ) continue;
                    anc[i][u] = anc[i - 1][k];
                    maxcost[i][u] = max( maxcost[i - 1][u], maxcost[i - 1][k] );
                }
    }
    int query(int p, int q){
        if( depth[ p ] < depth[ q ] ) swap( p, q );
        int hibit;
        for(hibit = 1; ( 1 << hibit ) <= depth[p]; ++hibit); --hibit;
        int ans = -INF;
        for(int i = hibit; i >= 0; --i)
            if( depth[ p ] - ( 1 << i ) >= depth[ q ] ){
                ans = max( ans, maxcost[i][p] );
                p = anc[i][p];
            }
        if( p == q ) return ans;
        for(int i = hibit; i >= 0; --i)
            if( anc[i][p] != -1 && anc[i][p] != anc[i][q] ){
                ans = max( ans, maxcost[i][p] ); p = anc[i][p];
                ans = max( ans, maxcost[i][q] ); q = anc[i][q];
            }
        ans = max( ans, cost[p] );
        ans = max( ans, cost[q] );
        return ans;
    }
} lca;

void dfs(int u, int fa, int depth){
    lca.depth[u] = depth;
    for(Edge &e: G[u]){
        if( e.v == fa ) continue;
        lca.fa[ e.v ] = u;
        lca.cost[ e.v ] = e.c;
        dfs( e.v, u, depth + 1 );
    }
}

void solve(){
    mst.solve();
    dfs( 1, -1, 0 );
    lca.preprocess();
    scanf("%d", &q);
    while( q-- ){
        int x, y; scanf("%d%d", &x, &y);
        printf("%d\n", lca.query( x, y ));
    }
}

int main(){
    while( scanf("%d%d", &n, &m) == 2 && n ){
        if( kase++ ) puts("");
        for(int i = 0; i < m; ++i){
            int u, v, c; scanf("%d%d%d", &u, &v, &c);
            es[i] = (Edge){ u, v, c };
        }
        solve();
    }
    return 0;
}