UVa 11354 邦德（最小瓶颈路+LCA）

https://vjudge.net/problem/UVA-11354

题意：

有n个城市m条道路，每条道路有一个危险系数。先在有若干个询问，要求找到一条从s到t的路，使得途径所有边的最大危险系数最小。

思路：

最小瓶颈路肯定是在最小生成树上的。所有先求最小生成树。

然后将它转化成有根树，让fa[i]和cost[i]分别表示结点i的父亲编号和它与父亲之间的边权L[i]表示结点i的深度。

anc[i][j]表示结点i的第2^j级祖先的编号（j==0时候就是fa[i],如果第2^j祖先不存在，设为-1）。

maxcost[i][j]表示结点i和第2^j级祖先之间路径上的最大权值。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<string>
  6 #include<vector>
  7 #include<queue>
  8 #include<cmath>
  9 #include<map>
 10 using namespace std;
 11 typedef long long LL;
 12 const int maxn=50000+5;
 13 const int INF=0x3f3f3f;
 14 
 15 struct node
 16 {
 17     int u,v,d;
 18     bool operator < (const node& rhs) const
 19     {
 20         return d<rhs.d;
 21     }
 22 }edge[2*maxn];
 23 
 24 int n,m;
 25 int cnt;
 26 int p[maxn];
 27 vector<int> g[maxn];
 28 vector<int> c[maxn];
 29 
 30 int find(int x)
 31 {
 32     return x==p[x]?x:p[x]=find(p[x]);
 33 }
 34 
 35 struct LCA
 36 {
 37     int n;
 38     int fa[maxn];
 39     int cost[maxn];
 40     int L[maxn];
 41     int anc[maxn][25];  //结点i的第（1<<j)级祖先编号，anc[i][0]就是父亲fa[i],anc[i][j]=-1表示该祖先不存在
 42     int maxcost[maxn][25];  //结点i和它的(1<<j)级祖先之间的路径上的最大权值
 43 
 44     void preprocess()   //预处理
 45     {
 46         for(int i=0;i<n;i++)
 47         {
 48             anc[i][0]=fa[i]; maxcost[i][0]=cost[i];
 49             for(int j=1;(1<<j)<n;j++)  anc[i][j]=-1;
 50         }
 51         for(int j=1;(1<<j)<n;j++)
 52         {
 53             for(int i=0;i<n;i++)
 54                 if(anc[i][j-1]!=-1)
 55             {
 56                 int a=anc[i][j-1];
 57                 anc[i][j]=anc[a][j-1];
 58                 maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
 59             }
 60         }
 61     }
 62 
 63     int query(int p,int q)
 64     {
 65         int tmp, log, i;
 66         if(L[p] < L[q]) swap(p,q);
 67         for(log=1; (1<<log) <= L[p]; log++);  log--;
 68 
 69         int ans=-INF;
 70         for(int i=log; i>=0;i--)
 71             if(L[p]-(1<<i)>=L[q])    //让p和q处于同一层
 72         {
 73             ans=max(ans,maxcost[p][i]);
 74             p=anc[p][i];
 75         }
 76 
 77         if(p==q)   return ans;  //LCA为p
 78 
 79         for(int i=log;i>=0;i--)
 80             if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i])//否则，让p,q同时往上爬，保证爬的时候始终处于同一层
 81             {
 82                 ans=max(ans,maxcost[p][i]);p=anc[p][i];
 83                 ans=max(ans,maxcost[q][i]);q=anc[q][i];
 84             }
 85         ans=max(ans,cost[p]);
 86         ans=max(ans,cost[q]);
 87         return ans;  //LCA为fa[p]（或fa[q]）
 88     }
 89 }solver;
 90 
 91 void MST()
 92 {
 93     sort(edge,edge+cnt);
 94     int num=0;
 95     for(int i=0;i<cnt;i++)
 96     {
 97         int x=edge[i].u,y=edge[i].v;
 98         int u=find(x),v=find(y);
 99         if(u!=v)
100         {
101             p[u]=v;
102             g[x].push_back(y); c[x].push_back(edge[i].d);
103             g[y].push_back(x); c[y].push_back(edge[i].d);
104             if(++cnt==n-1)  break;
105         }
106     }
107 }
108 
109 void dfs(int u,int fa,int level)   //无根树转有根树
110 {
111     solver.L[u]=level;
112     for(int i=0;i<g[u].size();i++)
113     {
114         int v=g[u][i];
115         if(v!=fa)
116         {
117             solver.fa[v]=u;
118             solver.cost[v]=c[u][i];  //cost就是v点到其父亲结点的权值
119             dfs(v,u,level+1);
120         }
121     }
122 }
123 
124 int main()
125 {
126     //freopen("D:\input.txt","r",stdin);
127     int kase=1;
128     while(~scanf("%d%d",&n,&m) && n)
129     {
130         cnt=0;
131         for(int i=0;i<n;i++)  {p[i]=i;g[i].clear();c[i].clear();}
132         for(int i=0;i<m;i++)
133         {
134             int x,y,d;
135             scanf("%d%d%d",&x,&y,&d);
136             edge[cnt].u=x-1;
137             edge[cnt].v=y-1;
138             edge[cnt].d=d;
139             cnt++;
140         }
141         MST();
142         dfs(0,-1,0);
143         solver.n=n;
144         solver.preprocess();
145         int q;
146         if(kase++!=1)  puts("");
147         scanf("%d",&q);
148         while(q--)
149         {
150             int x,y;
151             scanf("%d%d",&x,&y);
152             printf("%d
",solver.query(x-1,y-1));
153         }
154     }
155     return 0;
156 }