UVA11354[Bond] 倍增求LCA+Kruskal求最小瓶颈生成树

题目链接

题意：给定一个无向带权图，有一些询问，问u，v点之间的路径上最大边权值的最小为多少？也就是问u，v之间的最小瓶颈路的最大边长为？

solution:先求出最小瓶颈生成树，再倍增求出u，v的LCA，顺便算出ans值。

最小瓶颈生成树详解

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 7;
const int M = 1e5 + 10;struct E{int u, v, w;
}e[M];struct Edge{int u, v, w;Edge(int u,int v,int w):u(u),v(v),w(w){};
}; vector<Edge> edges;
vector<int> G[N];void addeage(int u, int v, int w){edges.push_back(Edge(u,v,w));int kk=edges.size();G[u].push_back(kk-1);
}
int n, m;
int pa[N];int find(int x){int r=x;while( r!=pa[r] ) r=pa[r];int i=x, j;while( i!=pa[i] ) {j=pa[i];pa[i]=r;i=j;}return r;
}bool merge(int x, int y){x=find(x), y=find(y);if( x==y ) return false;pa[x]=y; return true;
}bool cmp(E a, E b){return a.w<b.w;
}void Kruskal(){sort(e,e+m,cmp);int num=0;for ( int i=1; i<=n; i++ ) pa[i]=i, G[i].clear();edges.clear();for ( int i=0; i<m; i++ )if( merge(e[i].u,e[i].v) && num<n-1 ){addeage(e[i].u,e[i].v,e[i].w);addeage(e[i].v,e[i].u,e[i].w);num++;} 
}int cost[N], dep[N], fa[N];void dfs(int u,int fat){for (int i=0; i<G[u].size(); i++ ){Edge e=edges[G[u][i]];int vv=e.v, ww=e.w;if( vv==fat ) continue;dep[vv]=dep[u]+1;cost[vv]=ww;fa[vv]=u;dfs(vv,u);}
}int anc[N][20], mx[N][20];
//————————倍增求LCA——————// 
void prepocess(){memset(anc,0,sizeof(anc));// anc[i][j]表 示 i 的 第 2^j 级 祖 先 是 谁 memset(mx,0,sizeof(mx)); // mx[i][j] 表 示 i 到 第 2^j 级 祖 先 路 径 上 最 大 值 for ( int i=1; i<=n; i++ ){anc[i][0]=fa[i]; mx[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=1; i<=n; i++ )if( anc[i][j-1]!=-1 ){int a=anc[i][j-1];anc[i][j]=anc[a][j-1];mx[i][j]=max( mx[i][j-1], mx[a][j-1]); // 有 点 像 ST 表 }
}int query(int p, int q){if( dep[p]<dep[q] ) swap(p,q);int lg, ans=0;for ( lg=1; (1<<lg)<=dep[p]; lg++ ); lg--;for ( int i=lg; i>=0; i-- ) if( dep[p]-dep[q]>=(1<<i) ){ans=max(ans, mx[p][i]);p=anc[p][i];                // p 往 上 跳 } if( p==q ) return ans;for ( int j=19; j>=0; j-- )if( anc[p][j]!=-1 && anc[p][j]!=anc[q][j] ){ans=max(ans, mx[p][j]); p=anc[p][j];    ans=max(ans, mx[q][j]); q=anc[q][j];    // p,q 一 起 跳 }ans=max(ans, cost[p]);ans=max(ans, cost[q]);return ans;
}
//——————————————————————————// 
int main(){int ka=0;while( scanf("%d%d", &n, &m )==2 ){if(ka>0) printf("\n"); ka++;for ( int i=0; i<m; i++ )scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);Kruskal();dep[1]=0; fa[1]=0;      dfs(1,0);prepocess();int Q;scanf("%d", &Q);while( Q-- ){int x, y;scanf("%d%d", &x, &y );printf("%d\n", query(x,y) );}} 
}