gym 101081F
题意：给出一个无向图，定义一条路径的价值为 这条路径上最大的边权值。 有 Q 个询问，每次询问两个点间所有路径价值的最小值。
tags： 最小生成树的应用。
最小瓶颈路 ：给定一个加权无向图，并给定无向图中两个结点u和v，求u到v的一条路径，使得路径上边的最大权值最小。
所有两个点间的最小路径价值就是在最小生成树上。 构出最小生成树后，求树上两点之间的最大边，这个倍增或树链剖分都可以解决。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 200005; int tot, head[N]; struct Edge { int from, to, w, next; bool friend operator < (Edge a, Edge b) { return a.w < b.w; } } e1[N], e2[N]; void Add(int u, int v, int w) { e2[tot]=(Edge){u,v,w,head[u] }; head[u]=tot++; } int n, m, q, fa[N]; int Find(int x) { return fa[x]==x ? x : fa[x]=Find(fa[x]); } bool Unite(int a, int b) { int faa=Find(a), fab=Find(b); if(faa==fab) return false; else { fa[fab]=faa; return true; } } int dep[N], p[N][30], mx[N][30]; void dfslca(int u, int fa, int w) { dep[u]=dep[fa]+1, p[u][0]=fa, mx[u][0]=w; for(int i=head[u]; i!=-1; i=e2[i].next) if(e2[i].to!=fa) dfslca(e2[i].to, u, e2[i].w); } void Initlca() { mes(mx, 0); mes(p, -1); mes(dep, 0); dep[0]=-1; dfslca(1, 0, 0); for(int j=1; (1<<j)<=n; ++j) for(int i=1; i<=n; ++i) if(p[i][j-1]!=-1) mx[i][j]=max(mx[i][j-1], mx[p[i][j-1]][j-1]), p[i][j]=p[p[i][j-1]][j-1]; } int solve(int a, int b) { int i, j, ans=0; if(dep[a] < dep[b]) swap(a, b); for(i=0; (1<<i)<=dep[a]; ++i) ; --i; for(j=i; j>=0; --j) if(dep[a]-(1<<j) >= dep[b]) ans=max(ans, mx[a][j]), a=p[a][j]; if(a==b) return ans; for(j=i; j>=0; --j) if(p[a][j]!=-1 && p[a][j]!=p[b][j]) { ans = max(ans, max(mx[a][j], mx[b][j])); a=p[a][j], b=p[b][j]; } return ans=max(ans, max(mx[a][0], mx[b][0])); } int main() { scanf("%d%d", &n, &m); mes(head, -1); tot=0; rep(i,1,n) fa[i] = i; int u, v, w; rep(i,1,m) { scanf("%d%d%d", &u, &v, &w); e1[i] = (Edge) {u,v,w,0 }; } sort(e1+1, e1+1+m); rep(i,1,m) if(Unite(e1[i].from, e1[i].to)) Add(e1[i].from, e1[i].to, e1[i].w), Add(e1[i].to, e1[i].from, e1[i].w); Initlca(); scanf("%d", &q); rep(i,1,q) { scanf("%d%d", &u, &v); printf("%d ", solve(u, v)); } return 0; }