HDU 2586 LCA-Tarjan

还是LCA-tarjan算法，跟POJ 1330做法基本类似，只是这个题目要求输出两个点的最短距离，其实利用LCA的性质，就是两个点分别到最近公共祖先的距离之和

一开始本来想用并查集把路径长度给找出来，但是不太好处理，原因是我刚好找到的这个点还没有加入到并查集中，（因为还没回溯上去），如果马上就合并，我还得把父亲传下来，还破坏了原有算法的结构（在孩子这里就进行了并查集合并操作），会产生奇怪的结果。。。

有个很简便又机智的方法，就是在dfs的过程中一边记录从rt到下面的点的距离dis，假设 A 和 B 的LCA 是C，那么我求的其实就是disA-disC+disB-disC,很机智吧

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int N =80000+10;

int vis[N/2],f[N/2],dis[N/2],ans[N/2];

int v[N],w[N],nt[N],ft[N/2];

struct node

{

    int v,id;

    node(int _v,int _id)

    {

        v=_v;

        id=_id;

    }

};

vector<node> Q[N/2];

int out[211];

int n,m,tot;

void init()

{

    tot=0;

    for (int i=0;i<=n+1;i++){

        ft[i]=-1;

        Q[i].clear();

        f[i]=i;

        dis[i]=0;

        vis[i]=0;

    }

}

void add(int x,int y,int c)

{

    v[tot]=y;

    w[tot]=c;

    nt[tot]=ft[x];

    ft[x]=tot++;

}

int findset(int x)

{

    if (x!=f[x]){

        f[x]=findset(f[x]);

    }

    return f[x];

}

int unionset(int a,int b)

{

    int r1,r2;

    r1=findset(a);

    r2=findset(b);

    if (r1==r2) return r1;

    f[r2]=r1;

    return r1;

}

void LCA(int x,int pre)

{

    ans[x]=x;

    for (int i=ft[x];i!=-1;i=nt[i]){

        int vx=v[i];

        if (vx==pre) continue;

        dis[vx]=dis[x]+w[i];

        LCA(vx,x);

        int rt=unionset(x,vx);

        ans[rt]=x;

    }

    vis[x]=1;

    for (int i=0;i<Q[x].size();i++){

        node tmp=Q[x][i];

        int vx=tmp.v;

        if (vis[vx]){

            out[tmp.id]=dis[x]+dis[vx]-2*dis[ans[findset(vx)]];

        }

    }

}

int main()

{

    int t,a,b,c;

    scanf("%d",&t);

    while (t--)

    {

        scanf("%d%d",&n,&m);

        init();

        for (int i=1;i<n;i++){

            scanf("%d%d%d",&a,&b,&c);

            add(a,b,c);

            add(b,a,c);

        }

        for (int i=0;i<m;i++){

            scanf("%d%d",&a,&b);

            Q[a].push_back(node(b,i));

            Q[b].push_back(node(a,i));

        }

        dis[1]=0;

        LCA(1,-1);

        for (int i=0;i<m;i++){

            printf("%d\n",out[i]);

        }

    }

    return 0;

}

巴特西

HDU 2586 LCA-Tarjan

最新文章

热门文章