zoj 3195 Design the city LCA Tarjan

题目链接 : ZOJ Problem Set - 3195

题目大意:

求三点之间的最短距离

思路:

有了两点之间的最短距离求法,不难得出:
对于三个点我们两两之间求最短距离 得到 d1 d2 d3
那么最短距离就是 d = ( d1 + d2 + d3 ) / 2
  • 要注意每个数组的范围大小,因为这个问题手抖敲错,TLE+RE一整页/(ㄒoㄒ)/~~
  • 用前向星来保存边和询问,空间卡的也很严
  • 如下图所示:所求路线为紫色,等于蓝色+黄色+绿色之和的一半

    代码:

    #include <bits/stdc++.h> using namespace std; const int maxn = 50005; const int maxm = 70005; struct node1 { int next,to,w; } e[maxn*2]; struct node2 { int next,to,id; } q[maxm*6]; int n,m,head1[maxn],head2[maxn],cnt1,cnt2,vis[maxn],f[maxn],res[maxm*6],dist[maxn]; inline void add1(int u, int v, int w) { e[cnt1].to=v; e[cnt1].w=w; e[cnt1].next=head1[u]; head1[u]=cnt1++; } inline void add2(int u, int v, int id) { q[cnt2].to=v; q[cnt2].id=id; q[cnt2].next=head2[u]; head2[u]=cnt2++; } inline void init() { cnt1=cnt2=0; memset(head1,-1,sizeof(head1)); memset(head2,-1,sizeof(head2)); memset(vis,0,sizeof(vis)); } inline int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); } inline void tarjan(int s) { vis[s]=1; f[s]=s; int t; for(int i=head1[s]; i!=-1; i=e[i].next) { if(!vis[t=e[i].to]) { dist[t]=dist[s]+e[i].w; tarjan(t); f[t]=s; } } for(int i=head2[s]; i!=-1; i=q[i].next) if(vis[t=q[i].to]) res[q[i].id]=dist[s]+dist[t]-2*dist[Find(t)]; } int main() { int cnt=0,u,v,w,x,y,z; while(~scanf("%d",&n)) { init(); for(int i=1; i<n; ++i) { scanf("%d %d %d",&u,&v,&w); add1(u,v,w); add1(v,u,w); } scanf("%d",&m); m*=3; for(int i=1; i<=m; ++i) { scanf("%d %d %d",&x,&y,&z); add2(x,y,i); add2(y,x,i); ++i; add2(x,z,i); add2(z,x,i); ++i; add2(y,z,i); add2(z,y,i); } dist[0]=0; tarjan(0); if(!cnt) cnt++; else printf("\n"); for(int i=1; i<=m; ++i) { printf("%d\n",(res[i]+res[i+1]+res[i+2])/2); i+=2; } } return 0; }
posted @ 2017-11-19 21:57 lemonbiscuit 阅读(...) 评论(...) 编辑 收藏