程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> BZOJ 2791 Poi2012 Rendezvous 倍增LCA

BZOJ 2791 Poi2012 Rendezvous 倍增LCA

編輯:關於C++

題目大意:給定一棵內向森林,多次給定兩個點a和b,求點對(x,y)滿足:

1.從a出發走x步和從b出發走y步會到達同一個點

2.在1的基礎上如果有多解,那麼要求max(x,y)最小

3.在1和2的基礎上如果有多解,那麼要求min(x,y)最小

4.如果在1、2、3的基礎上仍有多解,那麼要求x>=y

因此那個x>=y是用來省掉SPJ的,不是題目要求- -

容易發現:

如果a和b不在同一棵內向樹上,顯然無解,否則一定有解

定義根為從一個點出發能走到的第一個環上點,如果a和b的根相同,則到達LCA是最優的

否則到達的點一定是a的根和b的根中的一個,兩種情況都計算一下,取最優解即可

《倍增LCA萬年寫不對系列》

#include 
#include 
#include 
#include 
#define M 500500
using namespace std;
int n,q,T;
int a[M],v[M],on_ring[M],pos[M],size[M];
int fa[M][20],dpt[M],root[M];
void DFS(int x)
{
	v[x]=T;
	if(v[a[x]]==T)
	{
		int i,temp=1;
		for(i=x;temp==1||i!=x;i=a[i],temp++)
			on_ring[i]=T,pos[i]=temp,root[i]=i;
		size[T]=temp-1;
		return ;
	}
	if(!v[a[x]])
		DFS(a[x]);
	if(!on_ring[x])
	{
		fa[x][0]=a[x];
		dpt[x]=dpt[a[x]]+1;
		root[x]=root[a[x]];
	}
}
int LCA(int x,int y)
{
	int j;
	if(dpt[x]=dpt[y])
			x=fa[x][j];
	if(x==y) return x;
	for(j=19;~j;j--)
		if(fa[x][j]!=fa[y][j])
			x=fa[x][j],y=fa[y][j];
	return fa[x][0];
}
int Distance(int x,int y,int p)
{
	return (y-x+p)%p;
}
void Solve(int x,int y)
{
	if(on_ring[root[x]]!=on_ring[root[y]])
	{
		printf("%d %d\n",-1,-1);
		return ;
	}
	if(root[x]==root[y])
	{
		int lca=LCA(x,y);
		printf("%d %d\n",dpt[x]-dpt[lca],dpt[y]-dpt[lca]);
		return ;
	}
	int fx=root[x],fy=root[y];
	int x1=dpt[x]+Distance(pos[fx],pos[fy],size[on_ring[fx]]),y1=dpt[y];
	int x2=dpt[x],y2=dpt[y]+Distance(pos[fy],pos[fx],size[on_ring[fy]]);
	if(max(x1,y1)!=max(x2,y2))
	{
		if(max(x1,y1)>n>>q;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=n;i++)
		if(!v[i])
			++T,DFS(i);
	for(j=1;j<=19;j++)
		for(i=1;i<=n;i++)
			fa[i][j]=fa[fa[i][j-1]][j-1];
	for(i=1;i<=q;i++)
	{
		scanf("%d%d",&x,&y);
		Solve(x,y);
	}
	return 0;
}



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved