P5236 【模板】静态仙人掌(圆方图-仙人掌模板)

圆方树学习链接:http://immortalco.blog.uoj.ac/blog/1955

部分题解内容转自:
https://www.luogu.org/blog/NaCly-Fish-blog/solution-p5236
https://www.cnblogs.com/onioncyc/p/8315335.html

题目链接

https://www.luogu.org/problem/P5236

题目大意

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

解题思路

什么是仙人掌图?

任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。

什么是圆方图?

1、原图中的点都是圆点
2、对于每个环,新建一个方点;这个方点和环上其它圆点连成菊花图
3、对于不在环上的两个圆点,保留原图中的边
如图:
原图:
圆方图:
对于边权:
从一个点开始dfs,对于u→v的边:
若u,v都是圆点,则权值为原图中边权
若u为方点,则权值为v到u父亲的最短路
否则权值为0
然后,就可以像普通的树上那样进行求解了,需要注意的是:
若lca(u,v)为圆点,则两点间最短路转化为圆方树上dis[u]+dis[v]-2*dis[lca]。(向上延伸的路径,经过环则必然经过每个方点的x,计算无误)

若lca(u,v)为方点,则记u,v在方点连接的圆点A,B的子树内,那么两点间最短路为dis[u]+dis[v]-dis[A]-dis[B]+dis(A,B),dis(A,B)是A,B在环上的短侧路径。

代码

#include <bits/stdc++.h>
const int maxn=2e4+100;
using namespace std;
int n,m,q;
struct node{
    int v,w,nxt;
}edge[maxn*2],edgee[maxn*2];
int head[maxn],fa[maxn],low[maxn],b[maxn],s[maxn],id[maxn],nn;
int dis[maxn],headd[maxn],deep[maxn],dfn[maxn];
int f[maxn][20];
int tot,dfsnum,tott,aa,bb;
void init(){
    nn=0;
    tot=0;
    dfsnum=0;
    tott=0;
    memset(head,-1,sizeof(head));
    memset(headd,-1,sizeof(headd));
}
void add(int u,int v,int w){
    edge[tot]={v,w,head[u]};
    head[u]=tot++;
}
void addd(int u,int v,int w){
    edgee[tott]={v,w,headd[u]};
    headd[u]=tott++;
}
void solve(int u,int v,int w){
    //参数w为非树边的边权
    nn++;
    int pre=w,idd=0;
    for(int i=v;i!=fa[u];i=fa[i]){
        s[i]=pre;
        pre+=b[i];
        id[i]=idd++;
    }
    s[nn]=s[u];//把整个环的边权和存到方点上
    s[u]=0;
    for(int i=v;i!=fa[u];i=fa[i]){
        //找最短路,建树边
        addd(nn,i,min(s[i],s[nn]-s[i]));
        addd(i,nn,min(s[i],s[nn]-s[i]));
    }
}
void tarjan(int x,int father){
    dfn[x]=low[x]=++dfsnum;
    for(int i=head[x];i!=-1;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==father)continue;
        if(!dfn[v]){
            fa[v]=x;
            b[v]=edge[i].w;//把u->v的边权存到v上
            tarjan(v,x);
            low[x]=min(low[x],low[v]);
        }
        else low[x]=min(low[x],dfn[v]);
        if(low[v]>dfn[x]){//圆点之间的连边,保留原图中数据
            addd(x,v,edge[i].w);
            addd(v,x,edge[i].w);
        }
    }
    for(int i=head[x];i!=-1;i=edge[i].nxt){
        int y=edge[i].v;
        if(fa[y]!=x&&dfn[y]>dfn[x]){
            //找到非树边,然后建方点并连边
            solve(x,y,edge[i].w);
        }
    }
}
void dfs(int x,int father){
    for(int j=1;(1<<j)<=deep[x];j++){
        f[x][j]=f[f[x][j-1]][j-1];
    }
    for(int i=headd[x];i!=-1;i=edgee[i].nxt){
        int v=edgee[i].v;
        if(v!=father){
            f[v][0]=x;
            deep[v]=deep[x]+1;
            dis[v]=dis[x]+edgee[i].w;
            dfs(v,x);
        }
    }
}
int lca(int x,int y){
    if(deep[x]<deep[y])swap(x,y);
    int d=deep[x]-deep[y];
    for(int i=0;(1<<i)<=d;i++){
        if(d&(1<<i))
            x=f[x][i];
    }
    if(x==y)return x;
    for(int i=20;i>=0;i--){
        if((1<<i)<=deep[x]&&f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    aa=x;
    bb=y;
    return f[x][0];
}
int main()
{
    int q;
    cin>>n>>m>>q;
    init();
    int u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    nn=n;//方点从n开始建
    tarjan(1,0);//找环的同时建树
    dfs(1,0);//lca预处理
    while(q--){
        cin>>u>>v;
        w=lca(u,v);
        if(w<=n)//编号不大于n的节点,即是圆点
            cout<<dis[u]+dis[v]-2*dis[w]<<endl;
        else{
            //若p为方点,则需要找出p的两个儿子A,B,分别是u和v的祖先。由于A,B在一个环上,
            //所以dis(A,B)可以直接求(两种情况取min。此时答案为dis(A,B)+dis(A,u)+dis(B,v)
            long long ans=dis[u]+dis[v]-dis[aa]-dis[bb];
            if(id[aa]<id[bb])
                ans+=min(s[aa]+s[w]-s[bb],s[bb]-s[aa]);
            else ans+=min(s[bb]+s[w]-s[aa],s[aa]-s[bb]);
            cout<<ans<<endl;
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注