hdu 2874 (LCA)

虚拟赛的时候，一看是求任意两点的最短路，不管怎么优化都超时，最近做一些树的题目，这是求任意两点到最近公共祖先的距离，先用并差集判断是否联通，联通就求最近公共祖先，先把图建成一棵棵树，

#include<string.h>
#include<stdio.h>
#define N 10010
int father[N],dfs[N],n,vis[N],head[N],num,f[N],ans,dis[N];
struct edge
{
	int st,ed,next,w;
}E[N*2];
void addedge(int x,int y,int w)
{
	E[num].st=x;
	E[num].ed=y;
	E[num].w=w;
	E[num].next=head[x];
	head[x]=num++;
}
int find(int a)
{
	if(f[a]!=a)
		f[a]=find(f[a]);
	return f[a];
}
void dfs1(int u)
{
	int i,v;
	vis[u]=1;
	for(i=head[u];i!=-1;i=E[i].next)
	{
		v=E[i].ed;
		if(vis[v]==1)continue;
		father[v]=u;
		dfs[v]=dfs[u]+1;
		dis[v]=E[i].w;
		dfs1(v);
	}
	if(ans<dfs[u])
		ans=dfs[u];
}
int LCA(int x,int y)
{
	int sum=0;
	while(dfs[x]>dfs[y])
	{
		sum+=dis[x];
		x=father[x];
	}
	while(dfs[y]>dfs[x])
	{
		sum+=dis[y];
		y=father[y];
	}
	while(x!=y)
	{
		sum+=(dis[x]+dis[y]);
		x=father[x];
		y=father[y];
	}
	return sum;
}
int main()
{
	int i,j,k,x,y,m,ans,w;
	while(scanf("%d%d%d",&n,&m,&k)!=-1)
	{
		memset(head,-1,sizeof(head));
		num=0;
		for(i=1;i<=n;i++)
			f[i]=i;
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&x,&y,&w);
			addedge(x,y,w);
			addedge(y,x,w);
			x=find(x);
			y=find(y);
			if(x!=y)
				f[x]=find(y);
		}
		memset(vis,0,sizeof(vis));
		ans=1;
		for(i=1;i<=n;i++)
		{
			if(vis[i]==0)
			{				
				dis[i]=0;
				dfs[i]=ans;
				father[i]=i;
				dfs1(i);
				ans++;
			}
		}
		while(k--)
		{
			scanf("%d%d",&x,&y);
			if(find(x)!=find(y))
			{printf("Not connected\n");continue;}
			j=LCA(x,y);
			printf("%d\n",j);
		}
	}
	return 0;
}

补充：软件开发 , C++ ,

上一个：Strategic Game HDU
下一个：hdu1010——Tempter of the Bone（DFS+剪枝）