poj1330+hdu2586 LCA离线算法

整整花了一天学习了LCA，tarjan的离线算法，就切了2个题。
第一题，给一棵树，一次查询，求LCA。2DFS+并查集，利用深度优先的特点，回溯的时候U和U的子孙的LCA是U，U和U的兄弟结点的子孙们的LCA是U的父亲，结合每次询问，

3. hdu2586，求无相无环有权图，求俩点距离（n<=40000，最短路必然TLE），转化树（任意取一点为根），双向边保存，链式前向星保存边和权，DfS,

先记录下每次询问，用链式前向星保存，双向保存,第（i+1）/2条边即为第i次询问（一次询问记为双向边），最后用一个数组ans[i][3]来记录，ans[i][0]:第i次询问起点，依次ans[i][1],终点，ans[i][2],他们的LCA。DIS【i】,表根到I的距离，最后：dis[u]+dis[v]-2*dis[lca[u,v]]即可。

#include<iostream>  //只求一次询问 1330，水

#include<vector>

#include<cstdio>

using namespace std;

vector<vector<int> >edge(10001);

int from,to;int n; bool mark=0;

int fa[10001];int visited[10001];

int find(int x){return fa[x]=(x==fa[x]?x:find(fa[x]));}   //压缩路劲

void readin()

{

    scanf("%d",&n); mark=0;

    for(int i=0;i<=n;i++)   //初始化

        {

            visited[i]=1;

            fa[i]=i;

            edge[i].clear();

        }

    int begin,end;

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

     {

         scanf("%d%d",&begin,&end);

         edge[begin].push_back(end);

         visited[end]=0;             //不是根，这样标记出根。

     }

    scanf("%d%d",&from,&to);

}

void tarjan(int u)

{

    int len=edge[u].size();

    for(int i=0;i<len;i++)

    {

        int v=edge[u][i];

        if(visited[v]==0)

        {

            tarjan(v);

            if(mark)return;

            fa[v]=u;           //合并之

        }

    }

      visited[u]=1;            //回溯时标记！！！！！这时候表明它和它的孩子都已经被标记，离线LCA这样。

        if(u==from&&visited[to])    //查询询问，另外一个点是否已经访问，若访问了，以find(v)为他们的LCA

        {

            mark=1;

            printf("%d\n",find(to));return;

        }

        if(u==to&&visited[from])

        {

            mark=1;

            printf("%d\n",find(from));return;

        }

}

int main()

{

    int tcase;scanf("%d",&tcase);

    while(tcase--)

    {

        readin();

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

        {

           if(visited[i])           //从根开使

          {

               visited[i]=0;   //此处不忘把根标记回来！

              tarjan(i);

            break;

          }

        }

    }

    return 0;

}

#include<iostream>  //46MS(G++)     会了就水了，DIF 2

#include<vector>       //o（n+q）

#include<cstdio>

using namespace std;

struct edges     //边集

{

    int pre,to,w;

};

struct querys  //询问的边

{

    int pre,to;

};

int n;  int num_query;

int fa[40001];int visited[40001];

int dis[40001];int head[40001];int head2[40001];

int res[201][3];

vector<querys>que(401);

vector<edges>edge(80001);

int find(int x){return fa[x]=(x==fa[x]?x:find(fa[x]));}   //并查集+压缩路径优化之

void readin()

{

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

    for(int i=0;i<=n;i++)      //初始化，

        {

            head[i]=head2[i]=-1;

            visited[i]=0;

            fa[i]=i;

          dis[i]=0;

        }

    int begin,end,w;

    for(int i=0;i<2*(n-1);i++)   //读入边和询问，都双向读入

     {

         scanf("%d%d%d",&begin,&end,&w);

         edge[i].to=end;

         edge[i].w=w;

         edge[i].pre=head[begin];

         head[begin]=i;

         i++;

         edge[i].to=begin;

         edge[i].w=w;

         edge[i].pre=head[end];

         head[end]=i;

     }

     for(int i=1;i<=2*num_query;i++)   //询问也双向读入，防止只有一头的情况

     {

       scanf("%d%d",&begin,&end);

        que[i].to=end;

         que[i].pre=head2[begin];

         head2[begin]=i;

         i++;

         que[i].to=begin;

         que[i].pre=head2[end];

         head2[end]=i;

     }

}

void tarjan(int u,int father)      //算法关键.

{

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

    {

        int v=edge[i].to;

        if(visited[v]==0&&v!=father)    //不回走（father）

        {

            dis[v]=dis[u]+edge[i].w;          //沿路记录长度

            tarjan(v,u);                      //递归

            fa[v]=u;           //合并之

        }

    }

      visited[u]=1;                        //回溯时标记（标记了说明该店已经有祖先fa[u]值），

     for(int i=head2[u];i!=-1;i=que[i].pre)      //遍历询问U的边，若有询问。用前向星可以记录询问的编号又能降低复杂度（直接访问U来走）

    {

        if(visited[que[i].to])

          {

            res[(i+1)/2][0]=u;                   //记录起点，终点，他们的LCA，询问的编号（次序）是(i+1)/2

            res[(i+1)/2][1]=que[i].to;

            res[(i+1)/2][2]= find(que[i].to);

          }

    }

}

int main()

{

    int tcase;scanf("%d",&tcase);

    while(tcase--)

    {

        readin();

        tarjan(1,-1);

         for(int i=1;i<=num_query;i++)

         {

             printf("%d\n",dis[res[i][0]]+dis[res[i][1]]-2*dis[res[i][2]]);

         }

         //printf("\n");

    }

    return 0;

}

巴特西

poj1330+hdu2586 LCA离线算法

最新文章

热门文章