学习笔记 - Kruskal重构树

听起来非常高级,其实思路却非常简单


Part1. 什么是 Kruskal 重构树

(以下简称重构树)

Kruskal 生成树算法大家都知道,但是重构树就不一定了。普通的生成树算法只是把原图中的边贪心地加到生成树里面,而重构树是将加入生成树的边转成点边权转成点权 而建出来的一种与原图形态不同的树。

(下面举例都是最小生成树,最大生成树是相反的)

重构树的思想大概是这样:

  • 起初每个点都是一个连通块,且 代表这个连通块的点 都为这个点本身;
  • 先像 Kruskal 生成树一样把边从小到大排序;
  • 然后贪心地枚举每一条边 (u,v),如果这条边连接是不同连通块的点,就 新建一个点 t,把 t 的 点权设置为边权,并分别连接该点与 u、v 所在连通块的代表节点,然后把 t 设置为两个连通块合并后的代表节点。

这样,我们就得到了一棵重构树(森林,当原图不连通的时候)。不难发现,重构树中:叶子节点代表的是原图中的点,非叶子节点都是边。

与生成树算法不一样 —— 重构树是一棵 有根树


Part2. 重构树的性质

比较显然的:

  • 是一棵二叉树;

比较有用的:

  • 满足 堆性质(把叶子节点的点权视作0)—— 根的点权大于左右儿子。
  • 原图上的点 u,v 在重构树上的路径是原图中“最大边最小”的路径。
  • 原图上的点 u,v 在重构树上的 LCA 是原图中“最大边最小”的路径的 最大边

第一点是 Kruskal 生成树算法贪心的结果。第二点是最小生成树的性质,然后第三点结合一二两点即可得出。

这些性质使得重构树非常强大。能够配合 倍增 做一些限制了图论中诸如“限制 u,v 路径上的最大边不能超过xxx”的题目。


Part3. 例题 NOI2018 - 归程

(想不到 NOI2018 就考了这个,好像是一道送分题,正好可以用来了解重构树)

Part3/1. 题面

>> 传送门-UOJ393

Part3/2. 解析

首先可以想到先处理出每个点到 1 号点的最短距离。然后对于每一个询问,我们求的是:从给定的起点出发,不经过有积水的边能够到达的所有点中,到 1 号点距离最短的点。

我们把条件抽象一下 —— 若不走有积水的边,能从 u 到达 v,就说明 u 到 v 的“最小海拔最大”的路径上的最小海拔超过了水位线。于是就可以想到重构树。

按最大生成树来建立重构树,那么重构树就满足小根堆;重构树上上 u 到 v 的路径就是 u 到 v 的“最小海拔最大”的路径;u,v 的 LCA 就是该路径上的最小海拔。

于是我们从起点出发,不经过积水的边,能够到达的点在重构树上就是“从起点出发,不到达海拔小于等于水位线的点,能够到达的叶子节点(叶子节点表示原图中的点嘛)”。又因为小根堆的性质,不难发现能够到达的点是重构树上的一棵子树!

因此我们要找到这棵子树中:叶子节点所代表的原图上的点 与 1 的最短距离。因为是在子树中,所以 DFS 一遍就好了。

至于怎么找这棵子树?倍增找 起点 的 最浅的海拔高于水位线的祖先 即可,倍增的时候注意利用好堆性质。

Part3/3. 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=2e5,M=4e5;
typedef long long ll;
const ll INF=(1ll<<60);

int cas;
int n,m,fn,q,tmp;
int ch[N*2+3][2],val[N*2+3],pre[N*2+3][20];
ll dis[N+3],mn[N*2+3];
bool fix[N+3];

struct DSU{
int fa[N+3],head[N+3];
void Init(){
for(int i=1;i<=n;i++){
fa[i]=head[i]=i;
mn[i]=INF;
}
}
int FindFa(int u){
if(u==fa[u]) return u;
return fa[u]=FindFa(fa[u]);
}
bool Merge(int u,int v,int wgt){
int fu=FindFa(u),fv=FindFa(v);
if(fu==fv) return false;
fn++;
ch[fn][0]=head[fu];
ch[fn][1]=head[fv];
val[fn]=wgt;
head[fv]=fn;
fa[fu]=fv;
return true;
}
}D_;
struct GNODE{
int to,len;GNODE *nxt;
GNODE(){}
GNODE(int _t,int _l,GNODE *_n):to(_t),len(_l),nxt(_n){}
};
struct GRAPH{
GNODE pol[M*2+3],*ncnt,*head[N+3];
void Init(){
for(int i=1;i<=n;i++) head[i]=NULL;
ncnt=pol;
}
void AddEdge(int u,int v,int len){
GNODE *p=++ncnt,*q=++ncnt;
*p=GNODE(v,len,head[u]);head[u]=p;
*q=GNODE(u,len,head[v]);head[v]=q;
}
GNODE* operator [](int id){return head[id];}
}G_;
struct EDGE{
int u,v,wgt;
EDGE(){}
EDGE(int _u,int _v,int _w):u(_u),v(_v),wgt(_w){}
}E_[M+3];

bool cmpEDGE(const EDGE &A,const EDGE &B){return A.wgt>B.wgt;}
void Kruskal(){
sort(E_+1,E_+1+m,cmpEDGE);
for(int i=1;i<=m;i++)
D_.Merge(E_[i].u,E_[i].v,E_[i].wgt);
}
void Dijkstra(){
priority_queue< pair<ll,int> > que;
que.push(make_pair(dis[1]=0,1));
while(!que.empty()){
int u=que.top().second;que.pop();
if(fix[u]) continue;
fix[u]=true;
for(GNODE *it=G_[u];it;it=it->nxt){
int v=it->to;
if(!fix[v] && dis[v]>dis[u]+it->len)
que.push(make_pair(-(dis[v]=dis[u]+it->len),v));
}
}
}
ll DFS(int u,int fa){
pre[u][0]=fa;
for(int i=1;i<=19;i++)
pre[u][i]=pre[pre[u][i-1]][i-1];
if(u<=n) return mn[u]=dis[u];
return mn[u]=min(DFS(ch[u][0],u),DFS(ch[u][1],u));
}
void Init(){
memset(pre,0,sizeof pre);
memset(mn,0x3f,sizeof mn);
memset(fix,false,sizeof fix);
memset(dis,0x3f,sizeof dis);
memset(ch,0,sizeof ch);
G_.Init();
D_.Init();
fn=n;
}
int Fetch(int u,int lim){
for(int i=19;i>=0;i--)
if(pre[u][i] && val[pre[u][i]]>lim)
u=pre[u][i];
return u;
}
int main(){
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&m);
Init();
for(int i=1;i<=m;i++){
int len;
scanf("%d%d%d%d",&E_[i].u,&E_[i].v,&len,&E_[i].wgt);
G_.AddEdge(E_[i].u,E_[i].v,len);
}
Dijkstra();
Kruskal();
for(int i=fn;i;i--)
if(!pre[i][0])
DFS(i,0);
int vS;
scanf("%d%d%d",&q,&tmp,&vS);
long long las=-1;
while(q--){
int frm,hgt;
scanf("%d%d",&frm,&hgt);
if(las!=-1){
frm=(frm+tmp*las-1)%n+1;
hgt=(hgt+tmp*las)%(vS+1);
}
printf("%lld\n",las=mn[Fetch(frm,hgt)]);
}
}
return 0;
}

The End

Thanks for reading!

时间越过越快了……

0%