gym 101081F

题意：给出一个无向图，定义一条路径的价值为 这条路径上最大的边权值。 有 Q 个询问，每次询问两个点间所有路径价值的最小值。

tags： 最小生成树的应用。

最小瓶颈路 ：给定一个加权无向图，并给定无向图中两个结点u和v，求u到v的一条路径，使得路径上边的最大权值最小。   

所有两个点间的最小路径价值就是在最小生成树上。 构出最小生成树后，求树上两点之间的最大边，这个倍增或树链剖分都可以解决。

#include
     
      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  secondtypedef 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<
      
       <=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<
       
        <=dep[a]; ++i) ;   --i;    for(j=i; j>=0; --j)        if(dep[a]-(1<
        
         = 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\n", solve(u, v));    }    return 0;}