LCA最近公共祖先（least common ancestors）

#include"stdio.h"

#include"string.h"

#include"iostream"

#include"queue"

#define M 111111

using namespace std;

struct st

{

    int u,v,next,w;

}edge[M*2];

int rank[M],head[M],t,pre[M],use[M],dis[M];

void init()

{

    t=0;

    memset(head,-1,sizeof(head));

}

void add(int a,int b,int w)

{

    edge[t].u=a;

    edge[t].v=b;

    edge[t].w=w;

    edge[t].next=head[a];

    head[a]=t++;

}

void bfs(int s)

{

    queue<int>q;

    memset(use,0,sizeof(use));

    memset(rank,0,sizeof(rank));

    use[s]=1;

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(int i=head[u];i!=-1;i=edge[i].next)

        {

            int v=edge[i].v;

            if(!use[v])

            {

                use[v]=1;

                rank[v]=rank[u]+1;

                pre[v]=u;

                dis[v]=edge[i].w;

                q.push(v);

            }

        }

    }

}//用bfs对点进行分层

int targan(int a,int b)

{

    int sum=0;

    while(a!=b)

    {

        if(rank[a]>rank[b])

        {

            sum+=dis[a];

            a=pre[a];

        }

        else

        {

            sum+=dis[b];

            b=pre[b];

        }

    }

    return sum;

}//查找

/*int targan(int a,int b)

{

    if(a==b)

        return a;

    else if(rank[a]>rank[b])

        return targan(pre[a],b);

    else

        return targan(a,pre[b]);

}*/深搜写法

int main()

{

    int n,m,a,i,b,c;

    while(scanf("%d%d",&n,&m)!=-1)

    {

        init();

        while(m--)

        {

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

            add(a,b,c);

            add(b,a,c);

        }

        bfs(1);

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

            printf("%d ",rank[i]);

        while(scanf("%d%d",&a,&b)!=-1)

        {

            int ans=targan(a,b);

            printf("%d\n",ans);

        }

    }

}

巴特西

LCA最近公共祖先（least common ancestors）

最新文章

热门文章