首页 > 代码库 > HDU 2874 Connections between cities（LCA离线算法实现）
HDU 2874 Connections between cities（LCA离线算法实现）
http://acm.hdu.edu.cn/showproblem.php?pid=2874
题意：
求两个城市之间的距离。
思路：
LCA题，注意原图可能不连通。
如果不了解离线算法的话，可以看我之前博客写的解释http://www.cnblogs.com/zyb993963526/p/7295894.html
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn=10000+5; 17 const int M=1000010; 18 19 int n, m, c; 20 int etot,qtot; 21 int ehead[maxn]; 22 int qhead[maxn]; 23 int mark[maxn]; 24 int dis[maxn]; 25 int vis[maxn]; 26 27 int ans[M]; 28 int p[maxn]; 29 30 struct node 31 { 32 int v,w; 33 int next; 34 }e[2*maxn]; 35 36 struct Node 37 { 38 int v; 39 int index; 40 int next; 41 }query[2*M]; 42 43 void addEdge(int u, int v, int w) 44 { 45 e[etot].v=v; 46 e[etot].w=w; 47 e[etot].next=ehead[u]; 48 ehead[u]=etot++; 49 } 50 51 void addQuery(int u, int v, int i) 52 { 53 query[qtot].v=v; 54 query[qtot].index=i; 55 query[qtot].next=qhead[u]; 56 qhead[u]=qtot++; 57 } 58 59 int Find(int x) 60 { 61 return p[x]==x?x:p[x]=Find(p[x]); 62 } 63 64 void LCA(int u) 65 { 66 vis[u]=1; 67 for(int i=qhead[u];i!=-1;i=query[i].next) 68 { 69 int v=query[i].v; 70 if(vis[v] && !mark[Find(v)]) //mark数组是为了针对非连通图的情况 71 ans[query[i].index]=dis[u]+dis[v]-2*dis[Find(v)]; 72 } 73 74 for(int i=ehead[u];i!=-1;i=e[i].next) 75 { 76 int v=e[i].v; 77 if(!vis[v]) 78 { 79 dis[v]=dis[u]+e[i].w; 80 LCA(v); 81 p[v]=u; 82 } 83 } 84 } 85 86 int main() 87 { 88 //freopen("in.txt","r",stdin); 89 while(~scanf("%d%d%d",&n,&m,&c)) 90 { 91 etot=qtot=0; 92 memset(qhead,-1,sizeof(qhead)); 93 memset(ehead,-1,sizeof(ehead)); 94 for(int i=1;i<=n;i++) p[i]=i; 95 96 while(m--) 97 { 98 int u,v,w; 99 scanf("%d%d%d",&u,&v,&w);100 addEdge(u,v,w);101 addEdge(v,u,w);102 }103 104 for(int i=1;i<=c;i++)105 {106 int u,v;107 scanf("%d%d",&u,&v);108 addQuery(u,v,i);109 addQuery(v,u,i);110 }111 112 memset(ans,-1,sizeof(ans));113 memset(vis,0,sizeof(vis));114 memset(mark,0,sizeof(mark));115 for(int i=1;i<=n;i++)116 {117 if(!vis[i])118 {119 dis[i]=0;120 LCA(i);121 mark[i]=1;122 }123 }124 for(int i=1;i<=c;i++)125 {126 if(ans[i]==-1) puts("Not connected");127 else printf("%d\n",ans[i]);128 }129 }130 return 0;131 }
HDU 2874 Connections between cities（LCA离线算法实现）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。