7
31
2015
0

【生成树上LCA】NOIP2013 T3货车运输

自古T3出神题!自古3面出神曲!

我觉得这次T3的题很符合我的胃口←_←

题意:给定一个图,求两点间所有路径上最小边权的最大值。

初中写只会二分答案+判断连通性(能再蠢些么= =)

看了题解:该边一定出现在最大生成树上!(如下图,蓝、绿色表示最大生成树。若所求边边(红色)不在最大生成树上,则绿边上必有所有边权必大于红边(想想Kruskal),则路径可以优化)只需求树上路径的最小边权。

于是学了欢乐的树上倍增算法(基于LCA)。

先说LCA(最近公共祖先):即找树上两点公共祖先中最近的一个。

姿势:预处理出树上第i点往上寻2^j的节点编号(dfs+伪分治),存入p[i][j]。

若询问两点a、b高度相同,则从较大的j往下枚举至0,一旦p[a][j]!=p[b][j]则两点都往上跳2^j层(即a=p[a][j],b=p[b][j]),那么最后p[a][0]即所求答案。……①

若询问两点a、b高度不同,则让较深的一点按照上述姿势往上调至相同高度。……②

辣么问题来了,求路径最小边权怎么搞。

是时候表演真正的技术了:预处理出树上第i点往上寻2^j个节点路径上的最小值,在①②往上跳的过程中同步维护整个路径最小边权,KO(BTW:树上路径长度也是这么做的)

CODE(我写得奇丑无比):

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxm 50010
#define maxn 10010
#define INF 2000000000
using namespace std;

struct Edge
{
	int u,v,w;
};
Edge edges[maxm];
int r[maxm],n,m,f[maxn];
int GF(int x)
{
	return f[x]==x?x:f[x]=GF(f[x]);
}
int cmp(int a,int b)
{
	return edges[a].w>edges[b].w;
}
Edge Gra[maxn*2];int Size=0;
int next[maxm],first[maxn];
void AddEdge(int u,int v,int w)
{
	int m=++Size;
	Gra[m]=(Edge){u,v,w};
	next[m]=first[u];
	first[u]=m;
}
int p[maxn][15];//以i跳2^j格的点(交的时候用14也让我水过了,看来没用链卡我)
int w[maxn][15];//跳的范围内最小边权
int h[maxn];//每点深度= =
int dfs(int u)
{
	for (int i=first[u];i!=-1;i=next[i])
		if (!h[Gra[i].v])
		{
			Edge e=Gra[i];
			h[e.v]=h[u]+1;
			p[e.v][0]=u;
			w[e.v][0]=e.w;
			dfs(e.v);
		}
}
void init()
{
	for (int j=1;(1<<j)<=n;j++)
		for (int i=1;i<=n;i++)
			if (p[i][j-1]!=-1)
			{
				p[i][j]=p[p[i][j-1]][j-1];
				w[i][j]=min(w[i][j-1],w[p[i][j-1]][j-1]);
			}
}
int LCA(int a,int b)
{
	int i,ans=INF;
	if (GF(a)!=GF(b)) return -1;
	if (h[a]<h[b]) swap(a,b);
	for (i=0;(1<<i)<=h[a];i++);
	i--;
	for (int j=i;j>=0;j--)
		if (h[a]-(1<<j)>=h[b])
		{
			ans=min(ans,w[a][j]);
			a=p[a][j];

		}
	if (a==b) return ans;
	for (int j=i;j>=0;j--)
	{
		if (p[a][j]!=-1&&p[a][j]!=p[b][j])
		{
			ans=min(ans,w[a][j]);
			a=p[a][j];
			ans=min(ans,w[b][j]);
			b=p[b][j];
		}
	}
	ans=min(ans,w[a][0]);
	return min(ans,w[b][0]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)f[i]=i;
	for (int i=1;i<=m;i++)r[i]=i;
	for (int i=1;i<=m;i++)
	{
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		edges[i]=(Edge){u,v,w};
	}
	sort(r+1,r+1+m,cmp);
	for (int i=1;i<=n;i++)
		first[i]=-1;
	for (int i=1;i<=m;i++)
	{
		Edge e=edges[r[i]];
		int x=GF(e.u),y=GF(e.v);
		if (x!=y)
		{
			f[x]=y;
			AddEdge(e.u,e.v,e.w);
			AddEdge(e.v,e.u,e.w);
		}
	}
	h[1]=1;
	dfs(1);
	init();
	int q;
	scanf("%d",&q);
	for (int i=1;i<=n;i++)
		if (!h[i]) h[i]=INF;
	for (int i=1;i<=q;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		printf("%d\n",LCA(u,v));
	}
	return 0;
}
Category: NOIP | Tags: LCA 倍增 生成树 | Read Count: 351

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com