首页 > 代码库 > HDU 2586 LCA-Tarjan

HDU 2586 LCA-Tarjan

2024-07-16 18:49:54   213人阅读

还是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;}

　　

 


联系
我们