wa的代码。。纯dfs
1 /* 2 LCA 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 #include<queue> 10 #include<map> 11 #include<math.h> 12 #pragma comment(linker, "/STACK:16777216") 13 using namespace std; 14 typedef long long ll; 15 //typedef __int64 int64; 16 const int maxn = 40005; 17 const int inf = 0x7fffffff; 18 const double pi=acos(-1.0); 19 const double eps = 1e-8; 20 21 int dis[ maxn ],ace[ maxn ],deep[ maxn ],fa[ maxn ]; 22 int cnt,head[ maxn ]; 23 struct node{ 24 int u,next,val; 25 }edge[ maxn<<4 ]; 26 void init(){ 27 cnt = 0; 28 memset( head,-1,sizeof( head ) ); 29 memset( fa,0,sizeof( fa ) ); 30 } 31 void addedge( int a,int b,int c ){ 32 edge[ cnt ].u = b; 33 edge[ cnt ].val = c; 34 edge[ cnt ].next = head[ a ]; 35 head[ a ] = cnt++; 36 } 37 int find( int x,int y ){ 38 if( x==y ) return x; 39 if( deep[ x ]>deep[ y ] ) return find( fa[x],y ); 40 else return find( x,fa[y] ); 41 } 42 void dfs( int now,int now_father,int now_ace,int now_deep,int now_dis ){ 43 fa[ now ] = now_father; 44 ace[ now ] = now_ace; 45 deep[ now ] = now_deep; 46 dis[ now ] = now_dis; 47 for( int i=head[ now ];i!=-1;i=edge[ i ].next ){ 48 int v = edge[ i ].u; 49 if( fa[ v ]==0 ){ 50 dfs( v,now,now_ace,now_deep+1,now_dis+edge[ i ].val ); 51 } 52 } 53 } 54 int main(){ 55 int n,m; 56 scanf("%d%d",&n,&m); 57 int a,b,c; 58 char s[2]; 59 init(); 60 while( m-- ){ 61 scanf("%d%d%d%s",&a,&b,&c,s); 62 addedge( a,b,c ); 63 addedge( b,a,c ); 64 } 65 for( int i=1;i<=n;i++ ){ 66 if( fa[i]==0 ){ 67 dfs( i,-1,i,0,0 ); 68 } 69 } 70 int k; 71 scanf("%d",&k); 72 while( k-- ){ 73 scanf("%d%d",&a,&b); 74 int father = find( a,b ); 75 printf("%d\n",dis[a]+dis[b]-2*dis[father]); 76 77 } 78 79 return 0; 80 }
tarjan算法。。
1 /* 2 LCA+tarjan 3 计算一棵树中任意两点之间的距离 4 */ 5 #include<stdio.h> 6 #include<string.h> 7 #include<algorithm> 8 #include<math.h> 9 using namespace std; 10 const int maxn = 40005; 11 int dis[ maxn ],vis[ maxn ],fa[ maxn ]; 12 struct node{ 13 int u,next,val; 14 }edge[ maxn<<2 ],ex_edge[ maxn ]; 15 int cnt,head[ maxn ],ex_cnt,ex_head[ maxn ]; 16 int ans[ maxn ]; 17 18 void init(){ 19 cnt = ex_cnt = 0; 20 memset( head,-1,sizeof( head ) ); 21 memset( ex_head,-1,sizeof( ex_head ) ); 22 memset( vis,0,sizeof( vis ) ); 23 memset( fa,-1,sizeof( fa ) ); 24 memset( dis,0,sizeof( dis ) ); 25 } 26 27 void addedge( int a,int b,int c ){ 28 edge[ cnt ].u = b; 29 edge[ cnt ].val = c; 30 edge[ cnt ].next = head[ a ]; 31 head[ a ] = cnt++; 32 } 33 void ex_addedge( int a,int b,int c ){ 34 ex_edge[ ex_cnt ].u = b; 35 ex_edge[ ex_cnt ].val = c; 36 ex_edge[ ex_cnt ].next = ex_head[ a ]; 37 ex_head[ a ] = ex_cnt++; 38 } 39 40 int find( int x ){ 41 if( fa[x]==-1 ) return x; 42 fa[x] = find( fa[x] ); 43 return fa[x]; 44 } 45 46 void tarjan( int u,int dist ){ 47 vis[ u ] = 1; 48 dis[ u ] = dist; 49 for( int i=ex_head[ u ];i!=-1;i=ex_edge[ i ].next ){ 50 int v = ex_edge[ i ].u; 51 if( vis[ v ]==1 ){ 52 ans[ ex_edge[ i ].val ] = dis[ u ]+dis[ v ]-2*dis[ find(v) ]; 53 } 54 } 55 for( int i=head[ u ];i!=-1;i=edge[ i ].next ){ 56 int v = edge[ i ].u; 57 if( vis[v]==0 ){ 58 tarjan( v,dist+edge[ i ].val ); 59 fa[ v ] = u; 60 } 61 } 62 } 63 64 int main(){ 65 int n,m; 66 while( scanf("%d%d",&n,&m)==2 ){ 67 int a,b,c; 68 char s[2]; 69 init(); 70 for( int i=0;i<m;i++ ){ 71 scanf("%d%d%d%s",&a,&b,&c,s); 72 addedge( a,b,c ); 73 addedge( b,a,c ); 74 } 75 int k; 76 scanf("%d",&k); 77 for( int i=0;i<k;i++ ){ 78 scanf("%d%d",&a,&b); 79 ex_addedge( a,b,i ); 80 ex_addedge( b,a,i ); 81 } 82 tarjan( 1,0 );//因为这是一棵树 任选1为root，tarjan( i,dis ):表示i到root的距离为dis 83 for( int i=0;i<k;i++ ){ 84 printf("%d\n",ans[i]); 85 } 86 } 87 return 0; 88 }