Hdu 2874 Connections between cities

时间：2022-01-09 20:02:41

题意：

城市 道路  没有环 不一定连通的树 求两城市的最短距离 设想一下就是很多小树  那好办

思路：

lca离线算法 然后有个技巧就是 每次我们tarjan一棵树不是最后树的节点都访问过并且孩子全能找到老爸嘛 那么我们只要做做做做 做到全部的城市都访问过了  就行了 反正你做这颗小树的时候又不会影响到其他树的

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,m;

const int N = ;

const int M = ;

int f[N],Next[*N],va[*N],wi[*N],Head[N];

int vis[N];

int nex[*M],to[*M],id[M],head[N],ans[M];

int find(int x)

{

    if(x!=f[x])f[x]=find(f[x]);

    return f[x];

}

int len,dis[N],l;

void add(int u,int v,int w)

{

    va[len]=v;

    wi[len]=w;

    Next[len]=Head[u];

    Head[u]=len++;

}

void add_x(int u,int v)

{

    to[l]=v;

    nex[l]=head[u];

    head[u]=l++;

}  

void lca(int u,int fa)

{

    f[u]=u;

    for(int i=Head[u];i!=-;i=Next[i])

    {int v=va[i],w=wi[i];

    if(v!=fa){

        dis[v]=dis[u]+w;

        lca(v,u);

        f[v]=u;

        }

    }

    vis[u]=;

    for(int i=head[u];i!=-;i=nex[i])

    {

        int v=to[i];

        if(vis[v])

        {//puts("sadasd");

        ans[i/]=find(v);

        }

    }

}

int main()

{

    int k;

    while(~scanf("%d%d%d",&n,&m,&k))

    {

        len=l=;

        memset(Head,-,sizeof Head);

        memset(head,-,sizeof head);

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

    {

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

        add(v,u,w);

    }

    dis[]=;

    for(int i=;i<k;i++)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        id[i]=u;

        add_x(u,v);

        add_x(v,u);

    }

memset(vis,,sizeof vis);

    memset(f,,sizeof f);

        memset(ans,-,sizeof ans);

        for(int i=;i<=n;i++)if(vis[i]==)lca(i,);

    for(int i=;i<l;i+=)

        {

            int a,b,c;

            a=to[i];

            b=id[i/];    

        if(find(a)!=find(b))puts("Not connected");

          else  {c=ans[i/];

         printf("%d\n",dis[a]+dis[b]-*dis[c]);}

    }

    }

}

相关文章