圆方树&仙人掌¶
仙人掌¶
定义
一张N个点，M条边的无向图，满足每条边都只在**至多一个简单环**中出现。
一定要保证环之间没有公共边
例题 #1¶
小L将取下一段永恒之树的树枝。
这里，我们将一段树枝抽象成一张N个点，M条边的无向图，满足每条边都只在**至多一个简单环**中出现。
小L 将对取下的树枝使用分解魔法，此后，树枝的每一个节点都会在一个时辰内随机的一个时刻，连同其连出去的边一起被分解。
在被分解的瞬间，每个节点会释放出等同于当时还与其连通的节点数量的能量，将这些能量求和就是X国的气运。
现在，小L想要知道，X国的气运期望会是多少。请求出X国气运的期望对998244353取模的结果。
例题 #2¶
给你一个有 \(n\) 个点和 \(m\) 条边的仙人掌图，和 \(q\) 组询问 每次询问两个点 \(u,v\)，求两点之间的最短路。
数据范围： $1\le n,q \le 10000 $$1\le m \le 20000 $\(1\le w \le 10^5\)
请注意时限为 \(300\text{ms}\)
注意：
本题n很大，不能用普通最短路做法！
由于仙人掌既有树的性质，但由于基环树有区别。如果是基环树的话，我们可以考虑断边，然后通过求出每个点的深度和lca(u,v)来快速求出u,v之间的距离。基环树和树的代码如下
const int N = 1e6 + 5;
const int INF = 1e9;
const int M = 200;
const int MOD = 1e9 + 7;
const double eps=1e-4;
/*
询问基环树上两个点之间的最近距离
首先如果没有环，那么我们只有一条路径，有环后我们就有2条路径。
我们可以选择一条边断掉，使得问题变成求树上路径的长度。但是这样我们会丢失答案。我们知道树上链条路径一定是互补的，
因此我们断掉了边V，那么另外一种情况一定是经过了边V(u,v)的。因此我们再求出两个点到u,v的距离即可。转移要判断那个到u，哪个到v
*/
struct node{
int v,w;
};
int s,t,w;
bool vis[N];
struct graph{
vector<node> e[N];
void add(int a,int b,int c){
e[a].pb({b,c});
e[b].pb({a,c});
}
int dep[N];
int fa[N][22];
int dis[N];
bool vvis[N];
void dfs(int x,int fa){
//找环，标记边
vis[x]=1;
for(auto v:e[x]){
if(v.v==fa)continue;
if(vis[v.v]){
// cdbg("Cr",v.v,x);
s=x,t=v.v;
w=v.w;
continue;
}
dfs(v.v,x);
}
}
void dfs2(int x,int f){
if(vvis[x])return ;
vvis[x]=1;
dep[x]=dep[f]+1;
for(auto v:e[x]){
if(x==s&&v.v==t)continue;
if(x==t&&v.v==s)continue;
if(v.v==f)continue;
fa[v.v][0]=x;
for(int i=1;i<=20;i++){
fa[v.v][i]=fa[fa[v.v][i-1]][i-1];
}
dis[v.v]=dis[x]+v.w;
dfs2(v.v,x);
}
}
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);
for(int i=20;~i;i--){
if(dep[fa[a][i]]>=dep[b])a=fa[a][i];
}
if(b==a)return a;
for(int i=20;~i;i--){
if(fa[a][i]!=fa[b][i]){
a=fa[a][i],b=fa[b][i];
}
}
return fa[a][0];
}
int getDis(int a,int b){
int anc=lca(a,b);
return dis[a]+dis[b]-2*dis[anc];
}
}e,g;
int query(int a,int b){
int res=e.getDis(a,b);
if(s){
res=min(res,g.getDis(a,s)+g.getDis(b,t)+w);
res=min(res,g.getDis(a,t)+g.getDis(b,s)+w);
}
return res;
}
void add(int a,int b,int c){
e.add(a,b,c);
g.add(a,b,c);
}
void solve(){
int n=rd,m=rd;
if(m>n)assert(0);
int q=rd;
for(int i=1;i<=m;i++){
int a=rd,b=rd,c=rd;
add(a,b,c);
}
e.dfs(1,0);
if(s){
e.dfs2(s,0);
g.dfs2(t,0);
}else{
e.dfs2(1,0);
g.dfs2(1,0);
}
while(q--){
int a=rd,b=rd;
cout<<query(a,b)<<endl;
}
}
signed main() {
// freopen("P2619_3.in","r",stdin);
// freopen("center.out","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
但是仙人掌上有不止一个环，所以我们用不了这种方法。所以我们考虑将图用某种方法变成一棵树（我们可以好好利用环与环之间互相独立这个性质！）
圆方树¶
定义
圆方树的建点、连边规则:
-
对于每个环，在环心建一个方点。这个**方点是不存在于原图的**。让环上一个割点做环的根，从割点向方点连一条权值为 \(0\) 的边，从方点向其它圆点连一条权值为 \(s\) 的边，\(s\) 是圆点到割点的最短路。这个方点与环上其它圆点连成菊花图。
-
对于不在环上的两个圆点，保留原图中的边权。
割点：图中的点 \(5,3,8\) 是割点。
我们来仔细考虑怎么将环变成菊花图。
红色点作为割点，其它边我们省略，只留下一个环。那么其作为圆方树就应该是右边这样。方点到其他点的距离代表着红色割点在环上到其他点的最短距离。如果一个环有不止一个割点，那么我们只选择第一个，即从 \(1\) 号点开始访问时访问到这个环的第一个割点。
注意，仙人掌是无向带环图，转化为圆方树后变成了一幅 DAG。
构建
我们可以使用 Tarjan 算法。
问题解决
这样，图上的最短路转化为树上的最短路，我们先用倍增法找 \(lca(u,v)\)，设其为 \(p\)。然后分类讨论:
-
若 \(p\) 为圆点，那答案就是树上这两点的距离 \(d[u]+d[v]-d[p]\times 2\)。
-
若 \(p\) 为方点，则需要找出 \(p\) 在环上的两个儿子 \(A,B\)，分别是 \(u\) 和 \(v\) 的祖先。答案应该为\(d(A,B)+d(A,u)+d(B,v)\)。
\(d(A,B)\)可以利用环长信息求解，\(len = \text{abs}(s[A]-s[B]), d(A,B) =\min(len,sc[A]-len)\)。其中，\(s[A]\) 是 \(A\) 到割点的环长，\(sc[A]\) 是 \(A\) 所在环的总长度。 \(d(A,u)=d[u]-d[A]\)
\(d(B,v)=d[v]-d[B]\)
我们重点考虑情况 2，在上上图中，我们假如要求 \(dis(6,9)\)，那么在原图上很容易发现是 \(9→8→5→7→6\)，\(dis=2+2+2+1=7\)。但是在圆方图上，\(5→6,9→8\) 路径都没有问题，但是 \(lca(6,9)\) 在圆方图上变成了一个方点，即其 \(lca\) 在一个环上。感性来想，一个环上所有点的深度可以认为是一样的，所以 \(6,9\) 有 \(2\) 个 \(lca\)，分别为 \(5,8\)。所以我们应该求出 \(5→8\) 之间的距离。但是在同一个环内求距离，我们就不能在圆方图上做了，只能在原图上做，否则会出错。
具体做法是，我们发现方点到 \(5,8\) 的距离实际上代表了割点（样例中为 \(3\)）到两个点的最短距离。那么我们就可以借助环长信息来求出距离了。具体实现请思考。
实际上就是我们从割点开始**有向地**访问每一个环上的点，如同中 \(s_a=a,s_b=a+b\)，那么点 \(a,b\) 之间的距离可能是 \(b\) 或者 \(a+c\)，我们求出 \(len1=abs(s_a-s_b)\)，\(len2=\) 环长 \(-len1\)，然后取 \(\min(len1,len2)\) 即可。
代码实现
注意这里我们需要建两幅图，一幅为原图，用来跑 tarjan 求出第 2 幅图，即圆方图。注意 tarjan 要建反向边，要用邻接表。并且 \(lca\) 应该在圆方图上跑而不是在原图上跑。
建立菊花图：
void build(int u,int v,int w){
int sum=w;
for(int k=v;k!=u;k=fa[k]){//遍历环上每一个点更新环的大小
sum+=fw[k];
}
s[u]=sz[u]=sum;
add2(u,++cnt2,0);//建方点
for(int k=v;k!=u;k=fa[k]){//遍历环上每一个点更新 点上记录的 环的大小
sc[k]=sum;
add2(cnt2,k,min(s[k],sum-s[k]));//建菊花点
}
}
Tarjan部分：
void tarjan(int u,int ine){//ine为入边编号
dfn[u]=low[u]=++tim;
for(int i=h1[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(dfs[v]){//访问过
if(i!=(ine^1))low[u]=min(low[u],dfn[v]);//成环
continue;
}
fa[v]=u;
fw[v]=w;
fe[v]=i;
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v])add2(u,v,w);//非环边
}
for(int i=h1[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(dfn[u]<dfn[v]&&fe[v]!=i)build(u,v,w);//建菊花图
}
}
Complete Code is here AC
/*////////ACACACACACACAC///////////
. Coding by Ntsc .
. FancyKnowledge .
. Prove Yourself .
/*////////ACACACACACACAC///////////
//头文件
#include<bits/stdc++.h>
//数据类型
#define int long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define pr pair<int,int>
#define pf first
#define ps second
#define pb push_back
//命名空间
using namespace std;
//常量
const int N=2e5+5;
const int M=1e3;
const int MOD=1e9+1;
const int INF=1e9;
const int IINF=1e18;
const db eps=1e-9;
//变量
int n,m,deg[N],b,c,p[N][22];
int fa[N],fw[N],s[N],fe[N];
int dep[N],d[N];
int tot,nt[N];
int dfn[N],low[N],tim;
int cn;
int A,B;//记录环上的两个lca
int sz[N];//记录每个点对应环的大小
int cnt=1,cnt2,h1[N],h2[N];
struct node{
int nxt,to,w;
}e[N],e2[N];
void add2(int u,int v,int w){
e2[++cnt2].to=v;
e2[cnt2].nxt=h2[u];
e2[cnt2].w=w;
h2[u]=cnt2;
}
void add(int u, int v,int w) {
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=h1[u];
h1[u]=cnt;
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
p[u][0]=fa;
for(int i=1;(1<<i)<=dep[u];i++)//二叉树，点i的深度即i/2
p[u][i]=p[p[u][i-1]][i-1];//第u个点向上2^i层的祖先就是第u个点的fa的上2^(i-1)层祖先
for(int i=h2[u];i;i=e2[i].nxt){//扫描出边
int v=e2[i].to;
if(v==fa)continue;//排除fa
d[v]=d[u]+e2[i].w;
dfs(v,u);
}
}
int lca(int a,int b){
if(dep[a]>dep[b])//统一切换为b比a深
swap(a,b);
for(int i=20;i>=0;i--)//b向上走到与a同层
if(dep[a]<=dep[b]-(1<<i))
b=p[b][i];
if(a==b)
return a;
for(int i=20;i>=0;i--){
if(p[a][i]==p[b][i])continue;//过头了
else a=p[a][i],b=p[b][i];
}
A=a,B=b;//假如是环，记录环上两个lca
return p[a][0];//最后a停在了lca的更深一层
}
void build(int u,int v,int w){
int sum=w;
for(int k=v;k!=u;k=fa[k]){//遍历环上每一个点更新环的大小
s[k]=sum;
sum+=fw[k];
}
// s[u]=sz[u]=sum;
add2(u,++cn,0);//建方点,cn初始值为n,故方点的编号>n,后面根据这个来判断lca是否为方点.不要写成cnt2
for(int k=v;k!=u;k=fa[k]){//遍历环上每一个点更新 点上记录的 环的大小
sz[k]=sum;
add2(cn,k,min(s[k],sum-s[k]));//建菊花点
}
}
void tarjan(int u,int ine){//ine为入边编号
dfn[u]=low[u]=++tim;
for(int i=h1[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(dfn[v]){//访问过
if(i!=(ine^1))low[u]=min(low[u],dfn[v]);//成环
continue;
}
fa[v]=u;
fw[v]=w;
fe[v]=i;
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v])add2(u,v,w);//非环边
}
for(int i=h1[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(dfn[u]<dfn[v]&&fe[v]!=i){
// cerr<<"build at u="<<u<<endl;
build(u,v,w);//建菊花图
}
}
}
int ask(int u,int v){
int p=lca(u,v);
// cerr<<"lca("<<u<<','<<v<<") is p="<<p<<endl;
if(p<=n)return d[u]+d[v]-2*d[p];//是圆点,注意这里d不是深度!
int l=abs(s[A]-s[B]);//A,B为两个lca
int dAB=min(l,sz[A]-l);
return dAB+d[u]+d[v]-d[A]-d[B];
}
signed main(){
int q;
cin>>n>>m>>q;
cn=n;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
tarjan(1,-1);
dfs(1,0);
while(q--){
int u,v;
cin>>u>>v;
cout<<ask(u,v)<<endl;
}
return 0;
}
DAG上的圆方树¶
我们可以使用tarjan算法求出vdcc的圆方树。
edcc的圆方树的造型如下：
-
对于割点，它是一个圆点。
-
对于一个vdcc（不包含割点），它是一个方点。
-
对于非割点的其他点，它们是原点，且悬挂在代表他们的vdcc的方点之下（菊花图）
void tarjan(int x){ //建圆方树
low[x]=dfn[x]=++dfn_cnt;
stk[++top]=x;
for(int i=0;i<son[x].size();++i){
int v=son[x][i];
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
if(low[v]==dfn[x]){
scc_cnt++;
int a;
do{
a=stk[top--];
E[a].push_back(scc_cnt);
E[scc_cnt].push_back(a);
}while(a!=v);
E[x].push_back(scc_cnt);
E[scc_cnt].push_back(x);
}
}
else low[x]=min(low[x],dfn[v]);
}
}
下面是一个vdcc圆方图的例题：
例题 #3 路径必经点¶
题目描述
给出n个点m条边的无向连通图，q次询问，每次查询两个点之间的必经点数量
多组数据，遇到0 0时结束程序
这里我们要注意，圆方图中有3种点：
-
belong=0的圆点→割点
-
belong=0的方点→代表一个vdcc
-
belong≠0的圆点，代表一个点
要求出路径上有几个必须经过的点，就是求路径上的割点，以及它们自身。所以实际上就是路径上圆点的个数（包含端点）。
特别注意belong相同不代表在同一个vdcc中，还可能是两个割点。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
#define ull unsigned long long
#define itn int
// #define inr int
// #define mian main
// #define iont int
#define rd read()
int read() {
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el = '\n';
const bool enable_dbg = 1;
template <typename T, typename... Args>
void dbg(T s, Args... args) {
if constexpr (enable_dbg) {
cerr << s;
if (1)
cerr << ' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) \
do { \
cerr << #x << " -> "; \
err(x); \
} while (0)
void err() { cerr << endl; }
template <template <typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v : a) cerr << v << ' ';
err(x...);
}
template <typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
vector<int> e[N], g[N];
int scc_cnt, dfn_cnt, top;
int dfn[N], low[N], stk[N];
void add(int a, int b) {
e[a].push_back(b);
e[b].push_back(a);
}
int belong[N];
void tarjan(int x) { //建圆方树
low[x] = dfn[x] = ++dfn_cnt;
stk[++top] = x;
for (int i = 0; i < e[x].size(); ++i) {
int v = e[x][i];
if (!dfn[v]) {
tarjan(v);
low[x] = min(low[x], low[v]);
if (low[v] == dfn[x]) {
scc_cnt++;
int a;
do {
a = stk[top--];
g[a].push_back(scc_cnt);
g[scc_cnt].push_back(a);
belong[a] = scc_cnt;
} while (a != v);
g[x].push_back(scc_cnt);
g[scc_cnt].push_back(x);
}
} else
low[x] = min(low[x], dfn[v]);
}
}
int dep[N];
int fa[N][22];
namespace LCA {
void dfs(itn x, int f) {
dep[x] = dep[f] + 1;
for (auto v : g[x]) {
if (v == f)
continue;
fa[v][0] = x;
for (int i = 1; i <= 20; i++) {
fa[v][i] = fa[fa[v][i - 1]][i - 1];
}
dfs(v, x);
}
}
int lca(int a, int b) {
if (dep[a] < dep[b])
swap(a, b);
for (int i = 20; ~i; i--) {
if (dep[fa[a][i]] >= dep[b])
a = fa[a][i];
}
if (a == b)
return a;
for (int i = 20; ~i; i--) {
if (fa[a][i] != fa[b][i])
a = fa[a][i], b = fa[b][i];
}
return fa[a][0];
}
} // namespace LCA
using namespace LCA;
int n, m;
void init() {
for (int i = 1; i <= n; i++) {
dfn[i] = 0;
low[i] = 0;
int sz = e[i].size();
while (sz--) {
e[i].pop_back();
}
}
for (int i = 1; i <= 2 * n + 1; i++) {
int sz = g[i].size();
while (sz--) {
g[i].pop_back();
}
}
top = 0;
dfn_cnt = 0;
}
void solve() {
init();
n = rd, m = rd;
scc_cnt = n;
if (n == 0)
exit(0);
for (itn i = 1; i <= m; i++) {
add(rd, rd);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i])
tarjan(i);
}
dfs(1, 0);
int q = rd;
while (q--) {
int a = rd, b = rd;
int anc = lca(a, b);
int ans = dep[a] + dep[b] - 2 * dep[anc];
write((ans >> 1) + 1);
puts("");
}
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T = 1;
while (T) {
solve();
}
return 0;
}
/*
8 10
4 8
3 4
1 2
1 3
2 3
1 5
5 6
5 7
6 7
7 8
5
4 8
2 3
2 5
1 5
5 8
*/