仙人掌相关问题的解法(2)-仙人掌最短路问题

[BZOJ2125]最短路

Description

给一个N个点M条边的连通无向图，满足每条边最多属于一个环，有Q组询问，每次询问两点之间的最短路径。

Input

输入的第一行包含三个整数，分别表示N和M和Q 下接M行，每行三个整数v，u，w表示一条无向边v-u，长度为w 最后Q行，每行两个整数v，u表示一组询问

Output

输出Q行，每行一个整数表示询问的答案

Sample Input

9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7

Sample Output

5
6

HINT

对于100%的数据，N<><>

    对多源最短路问题，树上的经典做法是两点到根的距离减去两倍的 LCA 到根的距离，那么我们使用圆方树将仙人掌图转化为树后就可以按相同思路解决了。

    然而我们发现原图的边权并没有很好地表现在我们建出来的圆方树上，所以我们首先解决边权问题：

1. 找到换的根；

2. 方点向环的根的连边的边权为 0 ；

3. 环上其他点向方点连边，边权为到环的根的最短路径长度。

    计算好边权后，对于两点的 LCA 是圆点的情况就可以直接按照树上的方法求距离了；而对于两点的 LCA 是方点的情况，其 LCA 是一个环，这两点一直向祖先走会到环上的两个不同位置，我们只需找到这两个位之间的到最短路。

具体方法：

1. Tarjan 找出所有的简单环，并记录环上信息备用，建圆方树；

   这里需要注意，上一道题的图比仙人掌图还要特殊，每个节点一定属于一个环，因此我们可以对于每个节点只访问一次即可；可对于一般情况，我们在发现一个点 u 的下一个点 v 满足： low[v]=dfn[u] 时，说明我们找到了一个环，且 u 为环首，这时我们要弹出从环尾到 v 的所有点，然而我们并不能确定是否要弹出 u （因为如果 u 还属于另外一个环，那就悲剧了），所以这是我们还有走回头路更新 low 值，判断是否弹出 v 。

   其实这里我们还有一种更好实现的处理方法：在 Tarjan 时维护一个边的栈，这样就可以免去许多细节处理问题。

    2. 维护圆方树的倍增数组，记录每个点到根的距离。

    3.倍增法求 LCA，若果 LCA 是环，还需要把两个点倍增到这个环上，在环上查询。

第一种实现 by PoPoQQQ

#include

#include

#include

#include

#include

#include

#define M 10100

#define INF 0x3f3f3f3f

using namespace std;

int n,m,q,cnt;

map f[M];

vector belong[M];

int dis[M];

vector rings[M];

int size[M];

map dist[M];

void Add(int x,int y,int z)

{

    if( f[x].find(y)==f[x].end() )

        f[x][y]=INF;

    f[x][y]=min(f[x][y],z);

}

namespace Cactus_Graph{

    int fa[M<><>

    pair second_lca;

    int Get_Depth(int x)

    {

        if(!fa[x][0]) dpt[x]=1;

        if(dpt[x]) return dpt[x];

        return dpt[x]=Get_Depth(fa[x][0])+1;

    }

    void Pretreatment()

    {

        int i,j;

        for(j=1;j<>

        {

            for(i=1;i<>

                fa[i][j]=fa[fa[i][j-1]][j-1];

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

                fa[i][j]=fa[fa[i][j-1]][j-1];

        }

        for(i=1;i<>

            Get_Depth(i);

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

            Get_Depth(i);

    }

    int LCA(int x,int y)

    {

        int j;

        if(dpt[x]<>

            swap(x,y);

        for(j=15;~j;j--)

            if(dpt[fa[x][j]]>=dpt[y])

                x=fa[x][j];

        if(x==y) return x;

        for(j=15;~j;j--)

            if(fa[x][j]!=fa[y][j])

                x=fa[x][j],y=fa[y][j];

        second_lca=make_pair(x,y);

        return fa[x][0];

    }

}

void Tarjan(int x)

{

    static int dpt[M],low[M],T;

    static int stack[M],top;

    map::iterator it;

    dpt[x]=low[x]=++T;

    stack[++top]=x;

    for(it=f[x].begin();it!=f[x].end();it++)

    {

        if(dpt[it->first])

            low[x]=min(low[x],dpt[it->first]);

        else

        {

            Tarjan(it->first);

            if(low[it->first]==dpt[x])

            {

                int t;

                rings[++cnt].push_back(x);

                belong[x].push_back(cnt);

                Cactus_Graph::fa[cnt][0]=n+x;

                do{

                    t=stack[top--];

                    rings[cnt].push_back(t);

                    Cactus_Graph::fa[n+t][0]=cnt;

                }while(t!=it->first);

            }

            low[x]=min(low[x],low[it->first]);

        }

    }

}

void DFS(int x)

{

    vector::iterator it,_it;

    static int stack[M];int i,j,top=0;

    for(it=rings[x].begin();it!=rings[x].end();it++)

        stack[++top]=*it;

    stack[++top]=*rings[x].begin();

    for(i=1;i<>

    {

        int p1=stack[i],p2=stack[i+1];

        size[x]+=f[p1][p2];

        if(i!=top-1)

            dist[x][p2]=dist[x][p1]+f[p1][p2];

    }

    i=2;j=top-1;

    while(i<>

    {

        if(dis[stack[i-1]]+f[stack[i-1]][stack[i]]<>

            dis[stack[i]]=dis[stack[i-1]]+f[stack[i-1]][stack[i]],i++;

        else

            dis[stack[j]]=dis[stack[j+1]]+f[stack[j+1]][stack[j]],j--;

    }

    for(_it=rings[x].begin(),_it++;_it!=rings[x].end();_it++)

        for(it=belong[*_it].begin();it!=belong[*_it].end();it++)

            DFS(*it);

}

int main()

{

    using namespace Cactus_Graph;

    int i,x,y,z;

    cin>>n>>m>>q;

    for(i=1;i<>

    {

        scanf('%d%d%d',&x,&y,&z);

        Add(x,y,z);Add(y,x,z);

    }

    Tarjan(1);

    Pretreatment();

    vector::iterator it;

    for(it=belong[1].begin();it!=belong[1].end();it++)

        DFS(*it);

    for(i=1;i<>

    {

        scanf('%d%d',&x,&y);

        int lca=LCA(n+x,n+y);

        if(lca>n) printf('%d\n',dis[x]+dis[y]-2*dis[lca-n]);

        else

        {

            int ans=dis[x]+dis[y]-dis[second_lca.first-n]-dis[second_lca.second-n];

            int temp=abs(dist[lca][second_lca.first-n]-dist[lca][second_lca.second-n]);

            ans+=min(temp,size[lca]-temp);

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

        }

    }

    return 0;

}

第二种实现 by virgil

#include

#include

#include

#include

#include 

#include

const int MAXN=1e4+5;

int N,M,Q;

int abs(int x){return (x<>

struct E{int next,to,val;} e[MAXN<3];int>

void addEdge(int u,int v,int w){e[++ecnt]=(E){G[u],v,w};G[u]=ecnt;}

void addEdge2(int u,int v,int w){addEdge(u,v,w);addEdge(v,u,w);}

void initCFS(){memset(G,0,sizeof(G));ecnt=0;}

struct A{int u,v,w;A(int u=0,int v=0,int w=0):u(u),v(v),w(w){};};

int dis[MAXN];bool inQ[MAXN];

std::queue que;

void SPFA(int S)

{

    int i;

    memset(dis,0x3f,sizeof(dis));

    que.push(S);dis[S]=0;inQ[S]=true;

    while(!que.empty())

    {

        int u=que.front();que.pop();

        inQ[u]=false;

        for(i=G[u];i;i=e[i].next)

        {

            int v=e[i].to;

            if(dis[v]>dis[u]+e[i].val)

            {

                dis[v]=dis[u]+e[i].val;

                if(!inQ[v]) que.push(v),inQ[v]=true;

            }

        }

    }

}

std::stack st;

int ringLen[MAXN],rcnt;

int belong[MAXN],ringRtDis[MAXN];

int anc[MAXN][20];

void addRing(int u,int v)

{

    rcnt++;

    while(st.top().u!=u&&st.top().v!=v)

    {

        A a=st.top();st.pop();

        ringRtDis[a.u]=ringRtDis[a.v]+a.w;

        ringLen[rcnt]+=a.w;

        if(a.u!=u) belong[a.u]=rcnt,anc[a.u][0]=u;

        if(a.v!=u) belong[a.v]=rcnt,anc[a.v][0]=u;

    }

    A a=st.top();st.pop();

    ringRtDis[a.u]=ringRtDis[a.v]+a.w;

    ringLen[rcnt]+=a.w;

    anc[a.v][0]=a.u;

}

int dfn[MAXN],low[MAXN],dcnt;

void tarjan(int u,int la)

{

    dfn[u]=low[u]=++dcnt;

    for(int i=G[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if(v==la) continue;

        if(!dfn[v])

        {

            st.push(A(u,v,e[i].val));

            tarjan(v,u);

            low[u]=std::min(low[u],low[v]);

            if(low[v]>=dfn[u])

                addRing(u,v);

        }else if(dfn[v]

    }

}

int dpt[MAXN];

int rebuild(int u,int la)

{

    dpt[u]=dpt[la]+1;

    for(int i=G[u];i;i=e[i].next)

        rebuild(e[i].to,u);

}

inline void initLCA()

{

    for(int i=1;(1<><>

        for(int j=1;j<>

            anc[j][i]=anc[anc[j][i-1]][i-1];

}

int calDis(int x,int y)

{

    int i;

    if(dpt[x]

    int xDis=dis[x],yDis=dis[y];

    int maxlogn=std::floor(std::log(N)/std::log(2));

    for(i=maxlogn;i>=0;i--)

        if(dpt[x]-(1=dpt[y])

            x=anc[x][i];

    if(x==y) return xDis-dis[x];

    for(i=maxlogn;i>=0;i--)

        if(anc[x][i]!=anc[y][i])

            x=anc[x][i],y=anc[y][i];

    if(belong[x]&&belong[x]==belong[y])

    {

        int xyDis=abs(ringRtDis[x]-ringRtDis[y]);

        int minDis=std::min(xyDis,ringLen[belong[x]]-xyDis);

        return xDis+yDis-dis[x]-dis[y]+minDis;

    }else return xDis+yDis-2*dis[anc[x][0]];

}

int main()

{   

    int i;

    scanf('%d%d%d',&N,&M,&Q);

    for(i=1;i<>

    {

        int u,v,w;scanf('%d%d%d',&u,&v,&w);

        addEdge2(u,v,w);

    }

    SPFA(1);

    tarjan(1,0);

    initLCA();

    initCFS();

    for(i=2;i<>

        addEdge(anc[i][0],i,0);

    rebuild(1,0);

    while(Q--)

    {

        int x,y;scanf('%d%d',&x,&y);

        printf('%d\n',calDis(x,y));

    }

    return 0;

}