【倍增LCA】 NOIP2013 T3货车运输 - cool's Blog

【倍增LCA】 NOIP2013 T3货车运输

cool posted @ 2015年9月13日 20:39 in 数据结构 , 255 阅读

人生第一道A掉的提高组T3= =

倍增+LCA 就能轻松AC了

但lbn大神让我去学树剖LCA 而我连树剖都不会 结果被大D一通

void Mul()
{
	for (int i = 1;i <= 14;i++) //14是logn
		for (int j = 1;j <= n;j++)
			if (p[j][i-1] != -1)
			{
				p[j][i] = p[p[j][i-1]][i-1];
				dis[j][i] = min(dis[j][i-1],dis[p[j][i-1]][i-1]);//距离
			}
}

 

 

int LCA(int a,int b)
{
	if (deep[a] < deep[b]) swap(a,b);
	int mina = 100000000,minb = 100000000;
	int t = deep[a] - deep[b];
	for (int i = 0;i <= 14;i++)
		if (t&(1 << i)) mina = min(mina,dis[a][i]),a = p[a][i];//到同一层
	if (a == b) return mina;
	for (int i = 14;i >= 0;i--)
		if (p[a][i] != -1&& p[a][i] != p[b][i])
		{
			mina = min(mina,dis[a][i]);
			a = p[a][i];
			minb = min(minb,dis[b][i]);
			b = p[b][i];
		}
	if (a == b) return min(mina,minb);
	return min(min(mina,dis[a][0]),min(minb,dis[b][0]));
}

 

Avatar_small
orz hhw 说:
2015年9月18日 13:24

这题并不能树剖LCA。。这题必须要维护出路上的最大值啊,还是倍增方便

Avatar_small
Flandre Scarlet 说:
2015年10月03日 18:53

@orz hhw: 线段树维护树链

Avatar_small
hhw 说:
2015年10月17日 20:17

@Flandre Scarlet: 多麻烦。。剖完还要写线段树,倍增可以直接维护


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee