UVA 11354 Bond（最小瓶颈路+倍增）

题意：问图上任意两点(u,v)之间的路径上，所经过的最大边权最小为多少？

求最小瓶颈路，既是求最小生成树。因为要处理多组询问，所以需要用倍增加速。

先处理出最小生成树，prim的时间复杂度为O(n*n)，kruskal为O(mlogm)。前者适合处理稠密图，后者适合处理稀疏图。

这里的倍增处理是值得记住的，在树上做多组询问；亦或是，将无向图缩点在询问，都是可以这样加速的。

注意：边权<=1e9

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<queue>
  5 #include<vector>
  6 #define clr(a,m) memset(a,m,sizeof(a))
  7 #define rep(i,a,b) for(int i=a;i<=b;i++)
  8 using namespace std;
  9 
 10 const int MAXN=55555;
 11 const int INF=1e9;
 12 const int POW =18;
 13 
 14 struct Edge{
 15     int u,v,c;
 16     bool operator < (const Edge rhs)const {
 17         return c>rhs.c;
 18     }
 19 };
 20 
 21 priority_queue<Edge>q;
 22 vector<int>G[MAXN];
 23 vector<Edge>edge;
 24 
 25 int fa[MAXN];
 26 
 27 int p[MAXN][POW],Max[MAXN][POW],d[MAXN];
 28 
 29 void init(int n)
 30 {
 31     while(!q.empty())
 32         q.pop();
 33 
 34     edge.clear();
 35     rep(i,1,n)
 36         G[i].clear();
 37 }
 38 
 39 void add(int u,int v,int c)
 40 {
 41     edge.push_back((Edge){u,v,c});
 42     int m=edge.size();
 43     G[u].push_back(m-1);
 44 }
 45 
 46 int find(int x)
 47 {
 48     return x==fa[x]?x:fa[x]=find(fa[x]);
 49 }
 50 
 51 void kruskal(int n)
 52 {
 53     int ans=0,cnt=0;
 54     rep(i,1,n)
 55         fa[i]=i;
 56     while(!q.empty())
 57     {
 58         Edge e=q.top();q.pop();
 59         int x=find(e.u);
 60         int y=find(e.v);
 61         if(x!=y){
 62             ans+=e.c;
 63             fa[x]=y;
 64             add(e.u,e.v,e.c);
 65             add(e.v,e.u,e.c);
 66         }
 67     }
 68 }
 69 
 70 void dfs(int u,int fa,int c)
 71 {
 72     d[u]=d[fa]+1;
 73     p[u][0]=fa;
 74     Max[u][0]=c;
 75 
 76     rep(i,1,POW-1){//写rep的原因，忘记-1了，又因为数组开的[POW],下标越界了，不过返回wa实在很无语
 77         p[u][i]=p[p[u][i-1]][i-1];
 78         Max[u][i]=max(Max[u][i-1],Max[p[u][i-1]][i-1]);//注意下标...写顺手写成Max[Max[u][i-1]][i-1]
 79     }
 80     int sz=G[u].size();
 81     rep(i,0,sz-1){
 82         Edge e=edge[G[u][i]];
 83         if(e.v==fa)
 84             continue;
 85         dfs(e.v,u,e.c);
 86     }
 87 }
 88 
 89 int lca( int a, int b )
 90 {
 91     int ans=-INF;
 92     if( d[a] > d[b] ) a ^= b, b ^= a, a ^= b;
 93     if( d[a] < d[b] ){
 94         int del = d[b] - d[a];
 95         for( int i = 0; i < POW; i++ )
 96             if(del&(1<<i)){
 97                 ans=max(ans,Max[b][i]);//注意处理顺序，先取最值，在更新当前点
 98                 b=p[b][i];
 99             }
100     }
101     if( a != b ){
102         for( int i = POW-1; i >= 0; i-- )
103             if( p[a][i] != p[b][i] ){
104                  ans=max(ans,Max[a][i]);
105                  ans=max(ans,Max[b][i]);
106                  a = p[a][i];
107                  b = p[b][i];
108             }
109         ans=max(ans,Max[a][0]);
110         ans=max(ans,Max[b][0]);
111         a = p[a][0];
112         b = p[b][0];
113     }
114     return ans;
115 }
116 
117 void LCA(int n)
118 {
119     int x,u,v;
120     clr(p,0);
121     d[1]=0;
122     dfs(1,1,0);
123     
124     scanf("%d",&x);
125     rep(i,1,x){
126         scanf("%d%d",&u,&v);
127         printf("%d
",lca(u,v));
128     }
129 }
130 
131 int main()
132 {
133     int n,m,cnt=0;
134     int u,v,c;
135     while(~scanf("%d%d",&n,&m))
136     {
137         if(cnt++)puts("");
138         init(n);
139         rep(i,1,m){
140             scanf("%d%d%d",&u,&v,&c);
141             q.push((Edge){u,v,c});
142         }
143         kruskal(n);
144         LCA(n);
145     }
146     return 0;
147 }
148 /*
149 9 8
150 1 2 10
151 1 3 20
152 2 4 20
153 2 5 30
154 3 6 30
155 3 7 10
156 4 8 30
157 5 9 10
158 36
159 1 2
160 1 3
161 1 4
162 1 5
163 1 6
164 1 7
165 1 8
166 1 9
167 2 3
168 2 4
169 2 5
170 2 6
171 2 7
172 2 8
173 2 9
174 3 4
175 3 5
176 3 6
177 3 7
178 3 8
179 3 9
180 4 5
181 4 6
182 4 7
183 4 8
184 4 9
185 5 6
186 5 7
187 5 8
188 5 9
189 6 7
190 6 8
191 6 9
192 7 8
193 7 9
194 8 9
195 */

View Code