uva 11865最小生成树瓶颈路(lca算法实现)(rmq在多校二中有一道题)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了uva 11865最小生成树瓶颈路(lca算法实现)(rmq在多校二中有一道题),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3057字,纯文字阅读大概需要5分钟。
内容图文
1 /* uva 11865 2 最小生成树瓶颈路 3 本来写了个BFS预判和LA5713一样,还线性优化了存储,结果还是T了, 4 不得不用LCA了,cry瞎 5 */ 6 #include<iostream> 7 #include<string.h> 8 #include<stdio.h> 9 #include<stdlib.h> 10 #include<cmath> 11 #include<algorithm> 12 #include<queue> 13 #include<stack> 14 #include<set> 15 #include<map> 16#define maxn 100100 17#define maxm 200100 18#define inf 999999999 19usingnamespace std; 20int n,m,ques; 21 vector<int>G[maxn]; 22 vector<int>D[maxn]; 23int nextint(){int x;scanf("%d",&x);return x;} 24struct Edge{ 25int u,v,d; 26booloperator<(const Edge& x ) const{ 27return d<x.d; 28 } 29}E[maxm],edges[maxm]; 30int p[maxn]; 31int findx(int x){ 32if (x==p[x]) return x;elsereturn p[x]=findx(p[x]); 33} 34void init() 35{ 36for(int i=0;i<m;i++){ 37int u,v,d; 38 u=nextint();v=nextint();d=nextint(); 39 u--,v--; 40 E[i]=(Edge){u,v,d}; 41 } 42 sort(E,E+m); 43 44for(int i=0;i<=n;i++) G[i].clear(); 45for(int i=0;i<=n;i++) D[i].clear(); 46} 47void MST() 48{ 49for(int i=0;i<=n;i++) p[i]=i; 50 51for(int i=0;i<m;i++){ 52int u=E[i].u,v=E[i].v,d=E[i].d; 53int pu=findx(u),pv=findx(v); 54if (pu==pv) continue; 55 p[pu]=pv; 56 G[u].push_back(v);D[u].push_back(d); 57 G[v].push_back(u);D[v].push_back(d); 58 } 59} 60 61int root,fa[maxn],cost[maxn],L[maxn]; 62int anc[maxn][20],maxcost[maxn][20]; 63struct Node{ 64int u,l; 65}; 66void dfs(int u,int f,int deep)//预处理fa,L,cost 67{ 68 L[u]=deep; 69for(int i=0;i<G[u].size();i++){ 70int d=D[u][i]; 71int v=G[u][i]; 72if (v!=f){ 73 fa[v]=u; 74 cost[v]=d; 75 dfs(v,u,deep+1); 76 } 77 } 78} 79void preprocess(){ 80 memset(maxcost,0,sizeof(maxcost)); 81 memset(anc,0,sizeof(anc)); 82for(int i=0;i<n;i++){ 83 anc[i][0]=fa[i];maxcost[i][0]=cost[i]; 84for(int j=1;(1<<j)<n;j++) anc[i][j]=-1; 85 } 86for(int j=1;(1<<j)<n;j++) 87for(int i=0;i<n;i++) 88if (anc[i][j-1]!=-1){ 89int a=anc[i][j-1]; 90 anc[i][j]=anc[a][j-1]; 91 maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]); 92 } 93} 94 95int query(int p,int q){ 96int tmp,log,i; 97if(L[p]<L[q]) swap(p,q); 98for(log = 1;(1<<log)<=L[p];log++);log--; 99100int ans=-inf; 101for(int i=log;i>=0;i--){ 102if (L[p]-(1<<i)>=L[q]){ans=max(ans,maxcost[p][i]);p=anc[p][i];} 103 } 104if (q==p) return ans; 105106for(int i=log;i>=0;i--){ 107if (anc[p][i]!=-1 && anc[p][i]!=anc[q][i]){ 108 ans=max(ans,maxcost[p][i]);p=anc[p][i]; 109 ans=max(ans,maxcost[q][i]);q=anc[q][i]; 110 } 111 } 112 ans=max(ans,cost[p]); 113 ans=max(ans,cost[q]); 114return ans; 115} 116int cas=0; 117int main() 118{ 119while(cin>>n>>m && n>0){ 120if (cas>0) printf("\n"); 121 init();MST(); 122 dfs(0,-1,0); 123 preprocess(); 124int Q; 125 cin>>Q; 126while(Q--){ 127int p,q; 128 p=nextint();q=nextint(); 129 printf("%d\n",query(p-1,q-1));//注意:节点必须从0开始编号130 } 131 cas++; 132 } 133return0; 134 }
原文:http://www.cnblogs.com/little-w/p/3597437.html
内容总结
以上是互联网集市为您收集整理的uva 11865最小生成树瓶颈路(lca算法实现)(rmq在多校二中有一道题)全部内容,希望文章能够帮你解决uva 11865最小生成树瓶颈路(lca算法实现)(rmq在多校二中有一道题)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。