本文共 1770 字，大约阅读时间需要 5 分钟。
题意：给你一张无向图，然后有若干组询问，让你输出a->b的最小瓶颈路。
思路：又是一道最小瓶颈路的题目。以前做过单组询问的，由郭华阳在集训队论文里提到的性质。在单组询问的时候只需要求出kurskal算大过程中第一次将他们合并的边就好了。但是对于这道题的多组询问，我们就不能那么处理了。在郭华阳的论文里讲到了一种方法每次合并时生成一个节点，把待合并的两个集合看成两颗子树，这样最终我们就只要对于询问的两个节点，求出他LCA的权值即可。
如图所示。但是这里我所采用的是另一种方法。就是dis[i][j]数组维护的是j号结点到2^i祖先的瓶颈路。这样我们把lca的查询过程稍稍修改一下就可以了。
代码如下：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #define MP(a, b) make_pair(a, b) 13 #define PB(a) push_back(a) 14 15 using namespace std; 16 17 typedef long long ll; 18 typedef pair pii; 19 typedef pair puu; 20 typedef pair pid; 21 typedef pair pli; 22 typedef pair pil; 23 24 const int INF = 0x3f3f3f3f; 25 const double eps = 1e-6; 26 const int LEN = 100000+10; 27 const int LOG_LEN = 25; 28 struct edge{ int from, to;ll val;}; 29 vector Map[LEN]; 30 edge e[LEN]; 31 int n, m, fa[LEN], q, qa, qb, parent[LOG_LEN][LEN], depth[LEN]; 32 ll dis[LOG_LEN][LEN]; 33 bool cmp(edge a, edge b){ return a.val depth[u]) swap(u, v); 89 ll ret = 0; 90 for(int i=0; i > i & 1) { 92 ret = max(ret, dis[i][u]); 93 u = parent[i][u]; 94 } 95 } 96 if(u==v) return ret; 97 for(int i=LOG_LEN-1; i>=0; i--){ 98 if(parent[i][u]!=parent[i][v]){ 99 ret = max(ret, dis[i][u]);100 ret = max(ret, dis[i][v]);101 u = parent[i][u];v = parent[i][v];102 }103 }104 ret = max(ret, dis[0][u]);105 ret = max(ret, dis[0][v]);106 return ret;107 }108 109 int main()110 {111 // freopen("in.txt", "r", stdin);112 113 int kase = 1;114 while(scanf("%d%d", &n, &m)!=EOF)115 {116 kase == 1? kase++:puts("");117 for(int i=0; i
转载于:https://www.cnblogs.com/shu-xiaohao/p/3532800.html
