正文
LCA（离线算法）
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
hdu4547
CD操作
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1010 Accepted Submission(s): 275
Problem Description
在Windows下我们可以通过cmd运行DOS的部分功能，其中CD是一条很有意思的命令，通过CD操作，我们可以改变当前目录。
这里我们简化一下问题，假设只有一个根目录，CD操作也只有两种方式：
1. CD 当前目录名\...\目标目录名 (中间可以包含若干目录，保证目标目录通过绝对路径可达)
2. 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操作。
数据保证合法，一定存在一个根目录，每个目录都能从根目录访问到。
每个样例首先一行是两个整数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
方法一：
1700ms
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define M 100009
#include"string"
#include"map"
#include"iostream"
using namespace std;
typedef struct st
{
int u,v,next,w;
}E[M*3];
E edge,edge1;
int dis[M],head[M],head1[M],t,t1,use[M],in[M];
int f[M];
int finde(int x)
{
if(x!=f[x])
f[x]=finde(f[x]);
return f[x];
}
void make(int u,int v)
{
int x=finde(u);
int y=finde(v);
if(x!=y)
f[x]=y;
}
void init()
{
t=t1=0;
memset(head,-1,sizeof(head));
memset(head1,-1,sizeof(head1));
}
void add(int u,int v)
{
edge[t].u=u;
edge[t].v=v;
edge[t].next=head[u];
head[u]=t++;
}
void add1(int u,int v,int w)
{
edge1[t1].u=u;
edge1[t1].v=v;
edge1[t1].w=w;
edge1[t1].next=head1[u];
head1[u]=t1++;
}
void dfs(int u)
{
use[u]=1;
int i;
for(i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!use[v])
{
dis[v]=dis[u]+1;
dfs(v);
f[v]=u;
make(u,v);
}
}
for(i=head1[u];i!=-1;i=edge1[i].next)
{
int v=edge1[i].v;
if(use[v])
{
edge1[i].w=edge1[i^1].w=f[finde(v)];
}
}
}
int main()
{
int T,i,m,n,x,y;
char ch1[60],ch2[60];
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
map<string,int>mp;
int k=1;
init();
memset(in,0,sizeof(in));
for(i=1;i<n;i++)
{
scanf("%s%s",ch1,ch2);
if(mp[ch1]==0)
{
x=k;
mp[ch1]=k++;
}
else
x=mp[ch1];
if(mp[ch2]==0)
{
y=k;
mp[ch2]=k++;
}
else
y=mp[ch2];
add(y,x);
in[x]++;
}
while(m--)
{
scanf("%s%s",ch1,ch2);
add1(mp[ch1],mp[ch2],0);
add1(mp[ch2],mp[ch1],0);
}
memset(use,0,sizeof(use));
memset(dis,0,sizeof(dis));
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=n;i++)
{
if(!in[i])
dfs(i);
}
for(i=0;i<t1;i+=2)
{
int u=edge1[i].u;
int v=edge1[i].v;
int mid=edge1[i].w;
int p;
if(v==mid)
p=0;
else
p=1;
printf("%d\n",dis[u]-dis[mid]+p);
}
}
}
方法二：
2700ms
#include"stdio.h"
#include"string.h"
#include"map"
#include"iostream"
#include"queue"
using namespace std;
#define M 100006
int dis[M];
int pre[M];
int rank[M],use[M],t,head[M];
int targan(int a,int b)
{
if(a==b)
return a;
else if(rank[a]>rank[b])
return targan(pre[a],b);
else
return targan(a,pre[b]);
}
struct st
{
int u,v,next;
}edge[M*3];
void init()
{
t=0;
memset(head,-1,sizeof(head)); }
void add(int u,int v)
{
edge[t].u=u;
edge[t].v=v;
edge[t].next=head[u];
head[u]=t++;
}
void bfs(int s)
{
queue<int>q;
memset(use,0,sizeof(use));
use[s]=1;
memset(rank,0,sizeof(rank));
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!use[v])
{
use[v]=1;
rank[v]=rank[u]+1;
q.push(v);
}
}
}
}
int main()
{
int w;
scanf("%d",&w);
while(w--)
{
map<string,int>mp;
int n,m,i;
char ch1[444],ch2[444];
init();
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
pre[i]=i;
int t=1;
for(i=1;i<n;i++)
{
scanf("%s%s",ch1,ch2);
if(!mp[ch1])
mp[ch1]=t++;
if(!mp[ch2])
mp[ch2]=t++;
pre[mp[ch1]]=mp[ch2];
dis[mp[ch1]]=1;
add(mp[ch2],mp[ch1]);
}
int tep=-1;
for(i=1;i<=n;i++)
if(pre[i]==i)
tep=i;
bfs(tep);
while(m--)
{
scanf("%s%s",ch1,ch2);
int ans=targan(mp[ch1],mp[ch2]);
if(ans!=mp[ch2])
printf("%d\n",rank[mp[ch1]]-rank[ans]+1);
else
printf("%d\n",rank[mp[ch1]]-rank[ans]);
}
}
return 0; }
