【算法】静态仙人掌
Tobiichi_Origami · · 个人记录
前置知识：
题目大意：
给定一棵仙人掌，让你求这棵仙人掌上两点之间的最短路。
解题思路：
在我们开始学习静态仙人掌之前，先需要了解仙人掌到底是一个什么东西：
如上图，仙人掌是一个无向连通图，任意一条边最多只能出现在一个环当中。
因为仙人掌是一个图，我们可以按照传统思想求多源最短路，但是会爆。所以我们用圆方树来将其转化成一棵树再来解决。
圆方树：
圆方树是一个有向有根树，从父节点连向子节点，并且这个树当中有两种点，圆点与方点。
圆点就是之前在仙人掌中的点。
而方点需要我们先将每个环的边全部断开，再找出每个环的根，具体可以用
而不在任何一个环当中的边边权不变，并且是一个割边，但是也都变成有向边。
因为这是一个有根树，所以我们将
最后保证与原仙人掌中的路径权值相等。
以上图为例，将它转化为一棵圆方树
当我们构建完圆方树后，就可以将最短路转化为求这两个点的最近公共祖先与他们之间的权值
- 以上图为例，当他们的最近公共祖先为圆点时，也就表示该路径与原图中路径权值相等且最近公共祖先存在于原图当中，所以就不用改变，即：
dis(u,v)=dis[u]+dis[v]-2×dis[lca(u,v)] 。
- 以上图为例，当他们的最近公共祖先为方点时，也就表示他们的最近公共祖先并不存在于原图当中，所以我们需要回到原图当中找到两边到达最近公共祖先之前的最后一个点，即方点与两条路径相交的两个孩子，我们用
A 和B 来表示。现在A 与B 在他们所属的环内只有两条路径，我们需要一个前缀和数组来存储他们的权值和。因为我们要求最短路，我们也就要求两条路径的最小值最后加上u 和v 分别到A 和B 的路径权值。
剩下的也就没什么了，对代码的解释的都在注释里了
贴代码
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,next,w;
}ed[1000001];
int he[1000001],tot;
int he2[1000001];
int dfn[1000001];
int low[1000001],idx;
int s[1000001],stot[1000001];//表示权值的前缀和与每个环内的权值和
int fa[1000001],fw[1000001];//父亲和与父亲之间的权值
int f[1000001][15];
int dep[1000001];
int dis[1000001];//与根的权值
int qwq,homo,num;//方点的两个儿子以及方点个数
int n,m,q;
void insert(int u,int v,int w)//建仙人掌
{
ed[tot].to=v;
ed[tot].w=w;
ed[tot].next=he[u];
he[u]=tot++;
}
void insert2(int u,int v,int w)//建圆方树
{
ed[tot].to=v;
ed[tot].w=w;
ed[tot].next=he2[u];
he2[u]=tot++;
}
void build(int u,int v,int w)
{
int sum=w;//从记录的这条边算起
for(int i=v;i!=u;i=fa[i])
{
s[i]=sum;//前缀和吗每次加上它到它父亲那条边的权值
sum+=fw[i];//更新sum
}
s[u]=stot[u]=sum;//因为u还没有被记录，所以赋值为更新完的sum。此时，sum加完环内所有权值。
insert2(u,++num,0);//向方点连边。因为是多余的点，所以num++
for(int i=v;i!=u;i=fa[i])
{
stot[i]=sum;//每个点都在这个环内
insert2(num,i,min(s[i],sum-s[i]));//向方点连一条最短路径，分别是一个优弧和劣弧
}
return ;
}
void tarjan(int u,int from)//割边
{
dfn[u]=low[u]=++idx;
for(int i=he[u];i!=-1;i=ed[i].next)
{
int v=ed[i].to;
if(!dfn[v])
{
fa[v]=u;fw[v]=ed[i].w;
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
insert2(u,v,ed[i].w);//这条边是割边，直接在圆方树中建边
}
else if(i!=(from^1))
low[u]=min(low[u],dfn[v]);
}
for(int i=he[u];i!=-1;i=ed[i].next)
{
int v=ed[i].to;
if(dfn[u]<dfn[v]&&fa[v]!=u)//表示v在以u为根的分量中，且这条边不在圆方树中，从u出去的边
build(u,v,ed[i].w);//建立方点再连接
}
return ;
}
void dfs(int u,int father)//预处理
{
dep[u]=dep[father]+1;
f[u][0]=father;
for(int i=1;(1<<i)<=dep[u];i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=he2[u];i!=-1;i=ed[i].next)
{
int v=ed[i].to;
dis[v]=dis[u]+ed[i].w;
dfs(v,u);
}
return ;
}
int LCA(int from,int to)//求LCA
{
if(dep[from]<dep[to])
swap(from,to);
int deep=dep[from]-dep[to];
for(int i=0;i<=13;i++)
{
if(deep&1)
from=f[from][i];
deep>>=1;
}
if(from==to) return to;
for(int i=13;i>=0;i--)
if(f[from][i]!=f[to][i])
{
from=f[from][i];
to=f[to][i];
}
qwq=from;homo=to;
return f[from][0];
}
int main()
{
memset(he,-1,sizeof(he));
memset(he2,-1,sizeof(he2));
scanf("%d %d %d",&n,&m,&q);num=n;//圆方树中至少有n个点
while(m--)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
insert(x,y,z);
insert(y,x,z);
}
tarjan(1,0);
dfs(1,0);
while(q--)
{
int x,y;
scanf("%d %d",&x,&y);
int lca=LCA(x,y);
if(lca<=n)
printf("%d\n",dis[x]+dis[y]-dis[lca]*2);//从源点到x+从源点到y-2*从源点到lca（不会建议画图）
else
{
int p=dis[x]-dis[qwq];
int q=dis[y]-dis[homo];
int minx=min(abs(s[qwq]-s[homo]),stot[qwq]-abs(s[qwq]-s[homo]));//一条路径与整个环内权值和减去的路径的最小值
printf("%d\n",p+q+minx);//输出
}
}
return 0;
}