学步园

题目链接:   poj 1986

题目大意:   给出一棵树,求a—b路径的长度

解题思路:   与hdu 2874类似

                  LCA离线查找最近公共祖先

                  dist[ ]求距离: 距离=dist[ a ] + dist[ b ] — 2*dist[ LCA(a,b) ]

代码:

//Final LCA离线 查找两点最短距离
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 50100
struct {
	int to,w,next;
}Hash[MAX<<2],Qes[MAX<<2];  //Hash是存在的边，Qes是需要查询点
int n,Index1,Index2,pre1[MAX],pre2[MAX],visit[MAX],ansetor[MAX],ans[MAX],dist[MAX];

void Add_edge(int a,int b,int c)   //建立树
{
	Hash[Index1].to=b,Hash[Index1].w=c;
	Hash[Index1].next=pre1[a];
	pre1[a]=Index1++;
}

void Add_Qes(int a,int b,int c)    //建立离线查询
{
	Qes[Index2].to=b,Qes[Index2].w=c;
	Qes[Index2].next=pre2[a];
	pre2[a]=Index2++;
}

int Find(int x)           //最近公共祖先查找
{
	int s,j;
	s=x;
	while(x!=ansetor[x])
		x=ansetor[x];
	while(s!=x)
	{
		j=ansetor[s];
		ansetor[s]=x;
		s=j;
	}
	return x;
}

void LCA(int u)     //离线查找最近公共祖先，并且在线更新当前点到根结点的距离
{
    int i,v;
    visit[u]=1;
    ansetor[u]=u;
    for(i=pre1[u];i!=-1;i=Hash[i].next)
    {
        v=Hash[i].to;
        if(!visit[v])        //如果此点没有访问过，则更新dist[]
        {
            dist[v]=dist[u]+Hash[i].w;
            LCA(v);          //回溯
            ansetor[v]=u;    //当前点的祖先暂时是u
        }
    }
    for(i=pre2[u];i!=-1;i=Qes[i].next)
    {
        v=Qes[i].to;
        if(visit[v])          //如果这个点之前访问过，那么它最近的祖先也就确定了
        {
            ans[Qes[i].w]=dist[u]+dist[v]-dist[ansetor[Find(v)]]*2;
        }
    }
}

int main()
{
	char ch[2];
	int m,k,i,a,b,c;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		Index1=Index2=0;
		memset(ans,-1,sizeof(ans));
		memset(pre1,-1,sizeof(pre1));
		memset(pre2,-1,sizeof(pre2));
		memset(dist,0,sizeof(dist));
		memset(visit,0,sizeof(visit));
		memset(ansetor,0,sizeof(ansetor));
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d%s",&a,&b,&c,ch);
			Add_edge(a,b,c);   //**如果树有结构的才用fathernum[]
			Add_edge(b,a,c);   //**
		}
		scanf("%d",&k);
		for(i=1;i<=k;i++)
		{
			scanf("%d%d",&a,&b);
			Add_Qes(a,b,i);
			Add_Qes(b,a,i);
		}
		for(i=1;i<=n;i++)
		{
			if(!visit[i])     //**没有访问过的点开始访问,如果树有结构的才从fathernum[]出发!
				LCA(i);
		}
		for(i=1;i<=k;i++)
		{
			printf("%d\n",ans[i]);
		}
	}
	return 0;
}