【基础练习】【倍增LCA】codevs1036 商务旅行题解

客官°小女子只卖身不卖艺 2022-08-09 00:50 163阅读 0赞

题目描述 Description

某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。

假设有N个城镇，首都编号为1，商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇，并且公路网络不会存在环。

你的任务是帮助该商人计算一下他的最短旅行时间。

输入描述 Input Description

输入文件中的第一行有一个整数N，1<=n<=30 000，为城镇的数目。下面N-1行，每行由两个整数a 和b (1<=a, b<=n; a<>b)组成，表示城镇a和城镇b有公路连接。在第N+1行为一个整数M，下面的M行，每行有该商人需要顺次经过的各城镇编号。

输出描述 Output Description

在输出文件中输出该商人旅行的最短时间。

样例输入 Sample Input

1 2

1 5

3 5

4 5

样例输出 Sample Output

这是一道很裸的LCA 乍一看似乎是图 但是边权只有1 而且符合树的结构 按顺序求出每两个点之间的最近路径相加即可

自从“水果街逛水果街2”参考了胜利一中sunshine神犇的代码 有了一些改进

先把代码放上

//codevs1036 商务旅行 LCA
    //copyright by ametake
    //since 19:20
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    using namespace std;
    
    const int maxn=30000+10;
    int depth[maxn],fa[maxn];
    int head[maxn],to[maxn*2],next[maxn*2];//twice again!!!
    int n,m;
    int et;
    int up[maxn][20];
    
    void add(int x,int y)
    {
    	et++;
    	to[et]=y;
    	next[et]=head[x];
    	head[x]=et;
    }
    
    void dfs(int now)
    {
    	int t=head[now];
    	while (t)
    	{
    		if (depth[to[t]])
    		{
    			t=next[t];
    			continue;
    		}
    		depth[to[t]]=depth[now]+1;//不能写depth[now]++ 这样depth[now]也会+1 
    		fa[to[t]]=now;
    		dfs(to[t]);
    		t=next[t];
    	}
    	return;
    }
    
    void doit()
    {
    	for (int i=1;i<=n;i++) up[i][0]=fa[i];
    	for (int j=1;j<=14;j++)
    	{
    		for (int i=1;i<=n;i++)
    		{
    			up[i][j]=up[up[i][j-1]][j-1];
    		}
    	}
    }
    
    int lca(int x,int y)
    {
    	if (depth[x]
           
            =0;i--) { if (up[x][i]!=up[y][i]) { x=up[x][i]; y=up[y][i]; } } return up[x][0]; } int main() { scanf("%d",&n); int x,y; memset(head,0,sizeof(head)); memset(depth,0,sizeof(depth)); for (int i=1;i

`具体来讲学习的是这一段核心代码 int lca(int x,int y) { 	if (depth[x]<depth[y]) swap(x,y); 	int dt=depth[x]-depth[y];     for (int i=0;i<=14;i++) 	{ 		if (dt&(1<<i)) x=up[x][i]; 	} 	if (x==y) return x; 	for (int i=14;i>=0;i--) 	{ 		if (up[x][i]!=up[y][i]) 		{ 			x=up[x][i]; 			y=up[y][i]; 		} 	} 	return up[x][0]; } 这里用了一个与运算，这个与运算的作用是判断某个数x的2的幂次方分解中是否含有2的i次方  在二进制的状况下 如果有2的i次方 那么在第i位是1 否则就是0 因此如果返回true说明有这个幂 sunshine神犇还有一个值得我学习的地方是这儿： if(deep[x]<(1<<i))break; 这个句子是放在搜索和转移中的 有效减少了层次过多问题 虽然时间似乎没节约多少 但总是好的 sunshine神犇的lca和我的在实现上有很大的不同，因为他是一边搜索一边倍增。首先倍增浅层的点，每次处理完这一层，搜索更深一层并进行深一层的状态转移倍增。当然我认为我们时间差别不大，但是sunshine神犇的似乎更高更妙一些。 马上就要闭关了。到时候一定要三更灯火五更鸡啊。看ACM前辈们每天只睡四五个小时，真是佩服。 其实我一天也就睡四五个小时，但是时间利用效率显然还有很大提升空间啊。 十一要是不能学文化课的话，就利用晚上什么的，虽然估计我没心情。如果实在不行的话 就请假 总之必须动静分离，不能混在一起。 闭关的时候，前期每天刷题练熟算法，一天至少A十道题吧。然后中午听听歌，晚上学学英语，听听歌，看看书。 《十八岁和其他》里，杨子说，他读高中的时候，每天捧着肖洛霍夫《静静的顿河》彻夜不眠。我现在几乎也是如此，不敢彻夜不眠，然而这部书实在引人入胜。 但是现阶段还是高考和OI是最重要的。下周开始，高考也放下，OI全力以赴。 所以加油吧。为了梦想，为了快乐。 ——纨绔不饿死，儒冠多误身`