Uva 11354 LCA 倍增祖先

題目鏈接：https://vjudge.net/contest/144221#problem/B

?

題意：找一條從 s 到 t ?的路，使得瓶頸路最小。

點的數目是10^4，如果向之前的方案求 maxcost數組，O(n*n)時間是過不了的，這個時候，用到了增倍祖先。

關于倍增祖先：http://m.w2bc.com/article/177601

我要補充的是，倍增祖先的優點，是在于倍增，他寫的案例，沒有體現出倍增，這里強調一下。有點像二分的思想；

?

利用倍增祖先初始化maxcost[i][j]數組，maxcost[i][j] 在倍增祖先里面表示的，結點 i 的第2^j級祖先之間的瓶頸。

用O(nlogn)初始化，然后，查詢是O(logn)。

#include <bits/stdc++.h>
using namespace std;const int maxn = 50000 + 10;
const int INF = 0x3f3f3f3f;
const int logmaxn = 20;int n,m;struct Edge
{int u,v,d;bool operator < (const Edge& rhs) const{return d < rhs.d;}
};Edge e[maxn];int pa[maxn];int Find_Set(int x)
{if(x!=pa[x])pa[x] = Find_Set(pa[x]);return pa[x];
}vector<int> G[maxn],C[maxn];struct LCA
{int n;int fa[maxn];int cost[maxn];int L[maxn];int anc[maxn][logmaxn];int maxcost[maxn][logmaxn];void preprocess(){for(int i=0; i<n; i++){anc[i][0] = fa[i];maxcost[i][0] = cost[i];for(int j=1; (1<<j)<n; j++)anc[i][j] = -1;}for(int j=1; (1<<j)<n; j++){for(int i=0; i<n; i++){if(anc[i][j-1]!=-1){int a = anc[i][j-1];anc[i][j] = anc[a][j-1];maxcost[i][j] = max(maxcost[i][j-1],maxcost[a][j-1]);}}}}int query (int p,int q){int log;if(L[p]<L[q]) swap(p,q);for(log=1; (1<<log)<=L[p]; log++);log--;int ans = -INF;for(int i=log; i>=0; i--){if(L[p]-(1<<i)>=L[q]){ans = max(ans,maxcost[p][i]);p = anc[p][i];}}if(p==q) return ans;        //lca 是 pfor(int i=log; i>=0; i--){if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){ans = max(ans,maxcost[p][i]);p = anc[p][i];ans = max(ans,maxcost[q][i]);q = anc[q][i];}}ans = max(ans,cost[p]);ans = max(ans,cost[q]);return ans;//LCA 是 fa[p] = fa[q];
    }};LCA solver;void dfs(int u,int fa,int level)
{solver.L[u] = level;for(int i=0; i<G[u].size(); i++){int v = G[u][i];if(G[u][i]!=fa){solver.fa[v] = u;solver.cost[v] = C[u][i];dfs(G[u][i],u,level+1);}}
}int main()
{//freopen("in.txt","r",stdin);int kase = 1;while(scanf("%d%d",&n,&m)==2&&n){for(int i=0; i<m; i++){int u,v,d;scanf("%d%d%d",&u,&v,&d);u--;v--;e[i] = (Edge){u,v,d};}sort(e,e+m);for(int i=0; i<n; i++){pa[i] = i;G[i].clear();C[i].clear();}for(int i=0; i<m; i++){int u = e[i].u;int v = e[i].v;int fx = Find_Set(u);int fy = Find_Set(v);if(fx!=fy){pa[fx] = fy;G[u].push_back(v);C[u].push_back(e[i].d);G[v].push_back(u);C[v].push_back(e[i].d);}}solver.n = n;dfs(0,-1,0);solver.preprocess();if(kase++!=1)puts("");int Q;scanf("%d",&Q);while(Q--){int u,v;scanf("%d%d",&u,&v);u--;v--;printf("%d\n",solver.query(u,v));}}return 0;
}

?