「重构树」Kruskal重构树入门笔记

Kruskal 重构树

Kruskal 重构树的过程就是在 Kruskal 算法 merge 的时候新建一颗树, 比如对于枚举到的边 (A, B):

image.png

我们新建一个点与其相连:

image.png

若边有边权, 则把 T 的 点权 设为其边权


我们来看看这样做的好处, 比如对于下面这个在最小生成树上的两个边:

image.png

经过上面的加点连边, 就可以得到:

image.png

其中 P 的点权为 3 , Q 的点权为 4

注意到Kruskal枚举的边的边权都是单调递增的, 所以按照上面的过程(最小生成树)构建的Kruskal重构树一定是个 大根堆

由于这是一棵树, 考虑这个树有什么特殊性质.

对于树上两点的 LCA, 在原图中的意义就是 两点间所有路径的最小边权的最大值


代码也很好写:

1
2
3
4
5
6
7
8
9
10
11
12
13
int ncnt;
void kruskal () {
std::sort(data + 1, data + m + 1, [] (const E &a, const E &b) -> bool { return a.w < b.w; });
ncnt = n;
up (i, 1, m) {
int _u = find(data[i].u), _v = find(data[i].v);
if (_u == _v) continue;
val[++ncnt] = data[i].w; // 点权
fa[_u] = fa[_v] = fa[ncnt] = ncnt;
add(_u, ncnt); add(ncnt, _u); // 加边
add(_v, ncnt); add(ncnt, _v); // 加边
}
}

下面来看一个简单的例题:

例题

「NOIP2013」货车运输

暂且就不放题面了, 因为太常见了

题面中求的是最大边权的最小值, 不过不影响重构树的使用

代码:

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
const int N = 200000 + 10;
const int M = 200000 + 10;

struct E {
int u, v, w;
E () {}
E (int _u, int _v, int _w) : u(_u) , v(_v) , w(_w) {}
};

struct Edge {
int v;
int next;
Edge () {}
Edge (int _v, int _n) : v(_v) , next(_n) {}
};

E data[M];

int tot;
int hd[N];
Edge e[M << 1];
int val[N];

inline void add (int u, int v) { e[++tot] = Edge(v, hd[u]); hd[u] = tot;}

int n, m;
int fa[N];

inline void init() { up (i, 1, n) fa[i] = i; }
inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int siz[N], vis[N];
int top[N], son[N];
int dep[N];
int Fa[N];

void dfs1 (int u, int fa = 0) {
siz[u] = vis[u] = 1;
for (int i = hd[u]; i; i = e[i].next) {
int v = e[i].v;
if (v == fa) continue;
Fa[v] = u;
dep[v] = dep[u] + 1;
dfs1(v, u);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}

void dfs2 (int u, int ctop = 0) {
top[u] = ctop;
if (son[u]) dfs2(son[u], ctop);
for (int i = hd[u]; i; i = e[i].next) {
int v = e[i].v;
if (v == Fa[u]) continue;
if (v ^ son[u]) dfs2(v, v);
}
}

int ncnt;
void kruskal () {
std::sort(data + 1, data + m + 1, [] (const E &a, const E &b) -> bool { return a.w > b.w; });
ncnt = n;
up (i, 1, m) {
int _u = find(data[i].u), _v = find(data[i].v);
if (_u == _v) continue;
val[++ncnt] = data[i].w;
fa[_u] = fa[_v] = fa[ncnt] = ncnt;
add(_u, ncnt); add(ncnt, _u);
add(_v, ncnt); add(ncnt, _v);
}
}

void pre() {
up (i, 1, ncnt) {
if (vis[i]) continue;
dfs1(find(i)); dfs2(find(i));
}
}

int lca (int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) u = Fa[top[u]];
else v = Fa[top[v]];
}
return dep[u] < dep[v] ? u : v;
}

int main () {
init();
n = read(); m = read();
int u, v, w;
up (i, 1, m) {
u = read(); v = read(); w = read();
data[i] = E(u, v, w);
}
init();
kruskal();
pre();
int q = read();
while (q --> 0) {
u = read(); v = read();
if (find(u) != find(v)) printf("-1\n");
else printf("%d\n", val[lca(u, v)]);
}
return 0;
}

「NOI2018」归程

题面仍然略了(

大概这类边权不好处理的就可以考虑转化为点权能不能做(

也是直接重构树

(Luogu数据好氵....建议去 uoj 交一下)

代码:

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
#define int long long

const int N = 500000 + 10;
const int M = 1000000 + 10;
const int logN = 20 + 2;

int n, m;

struct E {
int u, v, w;
E () {}
E (int _u, int _v, int _w) : u(_u) , v(_v) , w(_w) {}
};

struct Edge {
int v, w;
int next;
Edge () {}
Edge (int _v, int _w, int _n) : v(_v), w(_w), next(_n) {}
};

E data[M];

int tot;
int hd[N];
Edge e[M];
int val[N];

inline void add (int u, int v, int w) { e[++tot] = Edge(v, w, hd[u]); hd[u] = tot;}

int fa[N];
int f[N][logN];

int find (int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int d[N];
bool vis[N];

void dij (int S) {
memset (d, 0x3f, sizeof d); mem(vis);
std::priority_queue <std::pair<int, int> > q;
q.push(mp(0, S)); d[S] = 0;
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = hd[u]; i; i = e[i].next) {
int v = e[i].v;
if (d[v] > d[u] + e[i].w) {
d[v] = d[u] + e[i].w;
q.push(mp(-d[v], v));
}
}
}
}

void kru () {
std::sort (data + 1, data + m + 1, [] (const E &a, const E &b) -> bool { return a.w > b.w; });
int cnt = n;
up (i, 1, m) {
int _u = find(data[i].u), _v = find(data[i].v);
if (_u == _v) continue;
val[++cnt] = data[i].w;
fa[_u] = fa[_v] = f[_u][0] = f[_v][0] = cnt;
d[cnt] = std::min(d[_u], d[_v]);
}
for (int i = 1; (1 << i) <= cnt; i++)
up (j, 1, cnt) f[j][i] = f[f[j][i - 1]][i - 1];
}

inline int solve (int x, int y) {
down(i, 19, 0)
if (f[x][i] && val[f[x][i]] > y) x = f[x][i];
return d[x];
}

inline void init() {
tot = 0; mem(hd);
up (i, 1, 2 * n) fa[i] = i;
}

signed main () {
int T = read();
while (T --> 0) {
n = read(); m = read();
init();
int u, v, w, h;
up (i, 1, m) {
u = read(); v = read(); w = read(); h = read();
add (u, v, w); add(v, u, w);
data[i] = E(u, v, h);
}
dij(1);
kru();
int lst = 0;
int q, k, s, x, y;
q = read(); k = read(); s = read();
while (q --> 0) {
x = read(); y = read();
x = (x + k * lst - 1) % n + 1;
y = (y + k * lst) % (s + 1);
lst = solve(x, y);
print(lst); putchar('\n');
}
}
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!