首页 > 代码库 > HDU 4547 LCA倍增算法

HDU 4547 LCA倍增算法

2024-07-17 04:46:55   223人阅读

CD操作

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1111    Accepted Submission(s): 297


Problem Description
　　在Windows下我们可以通过cmd运行DOS的部分功能，其中CD是一条很有意思的命令，通过CD操作，我们可以改变当前目录。
　　这里我们简化一下问题，假设只有一个根目录，CD操作也只有两种方式：
　　
　　1. CD 当前目录名\...\目标目录名 (中间可以包含若干目录，保证目标目录通过绝对路径可达)
　　2. CD .. (返回当前目录的上级目录)
　　
　　现在给出当前目录和一个目标目录，请问最少需要几次CD操作才能将当前目录变成目标目录？
 

 

Input
输入数据第一行包含一个整数T(T<=20)，表示样例个数；
每个样例首先一行是两个整数N和M(1<=N,M<=100000)，表示有N个目录和M个询问；
接下来N-1行每行两个目录名A B(目录名是只含有数字或字母，长度小于40的字符串)，表示A的父目录是B。
最后M行每行两个目录名A B，表示询问将当前目录从A变成B最少要多少次CD操作。
数据保证合法，一定存在一个根目录，每个目录都能从根目录访问到。
 

 

Output
请输出每次询问的结果，每个查询的输出占一行。
 

 

Sample Input
2
3 1
B A
C A
B C
3 2
B A
C B
A C
C A
 

 

Sample Output
2
1
2
 
 
 
 
用map存储字符串，然后每输入一对字符串A、B，就找它们的最近公共祖先C，然后有4种情况：
1、A==B  则输出0
2、C！=A&&C！=B   则输出A到C的距离再加上1（1是从C到B，由题目知从一目录到该目录包含的所有目录走1步即可）
3、C==A   则直接输出1
4、C==B   则输出A到B的距离
 
 
代码：
  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #include <map>  5 #include <vector>  6 #include <queue>  7 #include <iostream>  8 using namespace std;  9 #define N 100005 10 #define M 20 11  12 int dep[N]; 13 int f[N][M]; 14 int visited[N]; 15 map<string,int>ma; 16 int n, m; 17 vector<int>ve[N]; 18  19  20 void init() 21 { 22     memset(dep,0,sizeof(dep)); 23     memset(f,0,sizeof(f)); 24     memset(visited,0,sizeof(visited)); 25     ma.clear(); 26     for(int i=0;i<=n;i++) ve[i].clear(); 27 } 28  29 void bfs(int root){ 30     queue<int>Q; 31     int i, u; 32     Q.push(root); 33     while(!Q.empty()){ 34         u=Q.front(); 35         Q.pop(); 36         if(visited[u]) continue; 37         visited[u]=1; 38         dep[u]=dep[f[u][0]]+1; 39         for(i=1;i<M;i++) f[u][i]=f[f[u][i-1]][i-1]; 40         for(i=0;i<ve[u].size();i++) Q.push(ve[u][i]); 41     } 42 } 43  44 int lca(int x,int y){ 45     if(dep[x]<dep[y]) swap(x,y); 46     int i, k=dep[x]-dep[y]; 47     for(i=0;i<M;i++){ 48         if(1<<i&k){ 49             x=f[x][i]; 50         } 51     } 52     if(x==y) return x; 53     for(i=M-1;i>=0;i--){ 54         if(f[x][i]!=f[y][i]){ 55             x=f[x][i]; 56             y=f[y][i]; 57         } 58     } 59     return f[x][0]; 60 } 61  62 main() 63 { 64     int i, j; 65     int k; 66     string s1, s2; 67     int t; 68     cin>>t; 69     while(t--){ 70         init(); 71         scanf("%d %d",&n,&m); 72         k=1; 73         for(i=1;i<n;i++){ 74             cin>>s1>>s2; 75             if(ma.find(s1)==ma.end()){ 76                 ma[s1]=k++; 77             } 78             if(ma.find(s2)==ma.end()){ 79                 ma[s2]=k++; 80             } 81             f[ma[s1]][0]=ma[s2]; 82             ve[ma[s2]].push_back(ma[s1]); 83         } 84         int root; 85         for(i=1;i<=n;i++){ 86             if(!f[i][0]){ 87                 root=i;break; 88             } 89         } 90         bfs(root); 91         while(m--){ 92             cin>>s1>>s2; 93             int node=lca(ma[s1],ma[s2]); 94             if(ma[s1]==ma[s2]){ 95                 printf("0\n"); 96             } 97             else if(node!=ma[s1]&&node!=ma[s2]) printf("%d\n",dep[ma[s1]]-dep[node]+1); 98             else if(node==ma[s1]) printf("1\n"); 99             else if(node==ma[s2]) printf("%d\n",dep[ma[s1]]-dep[ma[s2]]);100         }101         102     }103 }

 


联系
我们