【模板】静态仙人掌(圆方树)

传送门

Description

给你一个有(n)个点和(m)条边的仙人掌图，和(q)组询问
每次询问两个点(u,v)，求两点之间的最短路。

Solution

建出原图的圆方树，在这题中，两个点所组成的联通分量不是双联通分量

对于一条边(<u,v>)

(u,v)都是圆点，则边权为原图边权

父亲节点是方点，子节点是圆点，则边权是子节点到父亲的父亲圆点的最短路

(otherwise)，权值为(0)

这里要事先记下每个双联通分量（在本题中就是环）的边权和，以及每一条边在环上的位置

一个点可以属于多个环，而一条边只可能属于一个环

尽量采用维护边的方式，比如树剖时的(fa)指针，(mx)指针等等。

两个点的lca如果时圆点，则最短路就是它们到lca的距离和

如果是方点，则考虑在lca的位置暴力转弯

细节较多，不再赘述

Code

#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
const int MN=1e4+4,MQ=1e4+4,MM=2e4+5;
struct edge{int to;ll w;int nex;}e[MM<<1],E[MN<<2];int hr[MN],en,Hr[MN<<1],En=1;
inline void ins(int f,int t,ll w,int &end,int *h,edge *Ed)
{
    Ed[++end]=(edge){t,w,h[f]};h[f]=end;
    Ed[++end]=(edge){f,w,h[t]};h[t]=end;
}
int N,M,Q;
int dfn[MN],low[MN],st[MN],nx[MN],tp,dind;
int num,ss[MM<<2];ll val[MN<<1];
struct Node{int id,qz;};std::vector<Node> G[MN];
void tj(int x,int f)
{
    dfn[x]=low[x]=++dind;st[tp++]=x;register int i,tt;
    for(i=hr[x];i;i=e[i].nex)
    {
        if(!dfn[e[i].to])
        {
            tj(e[i].to,x);low[x]=min(low[x],low[e[i].to]);
            if(low[e[i].to]==dfn[x])
            {
                ++num;G[num-N].push_back((Node){x,0});
                ins(num,x,0,En,Hr,E);val[num]=e[i].w;ss[En]=ss[En^1]=tt=0;
                #define v st[tp-1]
                for(;st[tp]^e[i].to;G[num-N].push_back((Node){v,nx[v]}),--tp)
                    val[num]+=nx[v],ins(num,v,0,En,Hr,E),ss[En]=ss[En^1]=++tt;
                #undef v 
            }
            else if(low[e[i].to]>dfn[x]) tp--,ins(x,e[i].to,e[i].w,En,Hr,E);
            else nx[x]=e[i].w;
        }
        else if(e[i].to^f) low[x]=min(low[x],dfn[e[i].to]),nx[x]=e[i].w;
    }
}
int siz[MN<<1],mx[MN<<1],dep[MN<<1],top[MN<<1],fa[MN<<1];
ll Len[MN<<1];
void dfs1(int x,int f,int from)
{
    dep[x]=dep[f]+1;siz[x]=1;fa[x]=from;
    register int i;ll len;
    for(i=Hr[x];i;i=E[i].nex)if(E[i].to^f)
    {
        if(x>N&&!E[i].to<=N)
        {
            len=std::abs(G[x-N][ss[from]].qz-G[x-N][ss[i]].qz);
            E[i].w=E[i^1].w=min(val[x]-len,len);
        }
        dfs1(E[i].to,x,i);
        siz[x]+=siz[E[i].to];
        if(siz[E[i].to]>siz[E[mx[x]].to]) mx[x]=i;
    }
}
void dfs2(int x,int f,int tp)
{
    top[x]=tp;if(mx[x])Len[E[mx[x]].to]=Len[x]+E[mx[x]].w,dfs2(E[mx[x]].to,x,tp);
    register int i;
    for(i=Hr[x];i;i=E[i].nex)if(E[i].to!=f&&i!=mx[x])Len[E[i].to]=Len[x]+E[i].w,dfs2(E[i].to,x,E[i].to);
}
#define F(x) E[fa[x]^1].to
int LCA(int x,int y)
{
    while(top[x]!=top[y])dep[top[x]]>dep[top[y]]?x=F(top[x]):y=F(top[y]);
    return dep[x]<dep[y]?x:y;
}
int getnx(int x,int y)
{
    for(;top[x]!=top[y];)
    {
        if(F(top[x])==y) return fa[top[x]];
        else x=F(top[x]);
    }
    return mx[y];
}
ll dis(int x,int y)
{
    int lca=LCA(x,y);ll len,ans=Len[x]+Len[y]-(Len[lca]<<1);
    if(lca<=N) return ans;
    else x=getnx(x,lca),y=getnx(y,lca);
    ans-=E[x].w+E[y].w;len=std::abs(G[lca-N][ss[x]].qz-G[lca-N][ss[y]].qz);
    ans+=min(val[lca]-len,len);
    return ans;
}
int main()
{
    num=N=read(),M=read(),Q=read();
    register int i,x,y;
    for(i=1;i<=M;++i) x=read(),y=read(),ins(x,y,read(),en,hr,e);
    for(i=1;i<=N;++i) if(!dfn[i]) tj(i,0);
    for(i=1;i+N<=num;++i)for(x=1;x<G[i].size();++x) G[i][x].qz+=G[i][x-1].qz;
    dfs1(1,0,0);dfs2(1,0,1);
    while(Q--)
    {
        x=read();y=read();
        printf("%lld
",dis(x,y));
    }
    return 0;
}

Blog来自PaperCloud，未经允许，请勿转载，TKS！