抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

Kruskal重构树

发布于：2022年9月4日

图论

挺没用的😰，挺有用的😁，挺没用的😰，挺有用的 😁，挺没用的 😰，挺有😭😭

概述

回顾最小生成树的 Kruskal 算法

把每条边按边权排序，用并查集维护连通性，然后把边加入生成树中，直到珈😭乐 n-1 条边

我们每加入一条边时，实际上是合并了两个并查集，每次合并新建一个节点，节点的点权设为这条边的边权，左右儿子设为两个并查集的祖宗，最后得到了一个恰有 n 个 叶节点的二叉树，就是 kruskal 重构树


这张图的 Kruskal重构树长这样

性质

kruskal 重构树有一些很方便的性质

如果是最小生成树，那么重构树上两个节点的 LCA 的点权就是原图上两个节点之间所有简单路径最大边权的最小值

如果是最大生成树，那么重构树上两个节点的 LCA 的点权就是原图上两个节之间点所有简单路径最小边权的最大值

例题

NOIP提高2013 火车运输

一张无向图 nn 个点， mm 条边，每条边都有一个最大载重，每次询问从一个节点出发到达另一个节点能最大承受的重量

纯纯滴板子，对原图建最大生成树时建重构树，每次询问输出 LCA 即可

Code

LCA 我用的树剖，随便用，都可以用

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
#include <bits/stdc++.h>
#include <stdint.h>
#define MAXN 10005
#define MAXM 50005
#define ll long long
using namespace std;
int n, m;
struct edge
{
    int st, to, w;
}e[MAXM];

bool cmp(edge a, edge b)
{
    return a.w > b.w;    
}

int fa[MAXN << 1];
int find(int x)
{
    if(x == fa[x]) return x;
    else return fa[x] = find(fa[x]);
}

vector <int> g[MAXN << 1];
int faz[MAXN << 1];
int dis[MAXN << 1], vis[MAXN << 1];
int siz[MAXN << 1], son[MAXN << 1];
int dep[MAXN << 1], top[MAXN << 1];
void dfs1(int u, int dad)
{
    vis[u] = 1;
    siz[u] = 1; faz[u] = dad; dep[u] = dep[dad] + 1;
    for(int v : g[u])
    {
        if(v == dad) continue;
        dfs1(v, u); siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tup)
{
    top[u] = tup;
    if(son[u]) dfs2(son[u], tup);
    for(int v : g[u])
    {
        if(v == son[u] || v == faz[u]) continue;
        dfs2(v, v);
    }
}
int LCA(int u, int v)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] > dep[top[v]])
        u = faz[top[u]];
        else
        v = faz[top[v]];
    }
    return dep[u] < dep[v] ? u : v;
}

int main()
{
    scanf("%d%d", &n, &m);
    int cnt = n;
    for(int i = 1; i <= n; i++)
    fa[i] = i;
    
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[i] = edge{u, v, w};
    }
    sort(e+1, e+1+m, cmp);

    for(int i = 1; i <= m; i++)
    {
        int fx = find(e[i].st), fy = find(e[i].to);
        if(fx == fy) continue;
        fa[fx] = fa[fy] = ++cnt;
        fa[cnt] = cnt; 
        dis[cnt] = e[i].w;
        g[cnt].push_back(fx);
        g[cnt].push_back(fy);
        g[fx].push_back(cnt);
        g[fy].push_back(cnt);
    }
    for(int i = 1; i <= cnt; i++)
    {
        if(!vis[i])
        {
            int u = find(i);
            dfs1(u, 0); dfs2(u, u);
        }
    }
    int q; scanf("%d", &q);
    for(int i = 1; i <= q; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        int fu = find(u), fv = find(v);

        if(fu != fv) printf("-1\n");
        else printf("%d\n", dis[LCA(u, v)]);
    }
    
    return 0;
}

SCOI2013 摩托车交易

一张无向图 nn 个城市，mm 条道路， 现在你有一些黄金和 nn 个订单 ，要依次前往这 nn 个城市进行 买入/卖出 黄金的交易，但是每条道路对携带的黄金数量有一定限制，也存在一些城市能够互相抵达而且没有限制，询问每个卖出交易最大的交易额度

还是经典 两个节点之间所有简单路径最小边权的最大值 处理到达订单所在城市最多保留的黄金，对于那些特殊的节点，新建一个虚拟节点，把这些节点和虚拟节点都连一条限制特别大的便就行辣

Code 
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
140
141
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#define MAXN 500005
#define MAXM 2000005
#define ll long long
#define cjb 1919810114514843
using namespace std;
int n, m, q, cnt;
int a[MAXN];
ll b[MAXN];

struct edge
{
    int st, to;
    ll w;
}e[MAXM];
bool cmp(edge a, edge b)
{
    return a.w > b.w;
}

int fa[MAXM];
int find(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

ll dis[MAXM];
vector <int> g[MAXM];
void klskr()
{
    sort(e + 1, e + 1 + m, cmp);
    for(int i = 1; i <= m; i++)
    {
        int u = e[i].st, v = e[i].to;
        int fu = find(u), fv = find(v);
        if(fu == fv) continue;
        cnt++;
        fa[cnt] = fa[fv] = fa[fu] = cnt;
        dis[cnt] = e[i].w;
        g[cnt].push_back(fv);
        g[cnt].push_back(fu);
        g[fv].push_back(cnt);
        g[fu].push_back(cnt);
    }
    return;
}
//树剖LCA
int siz[MAXM], dep[MAXM], faz[MAXM];
int top[MAXM], son[MAXM];
    
void dfs1(int u, int dad)
{
    siz[u] = 1;
    faz[u] = dad;
    dep[u] = dep[dad] + 1;
    for(int v : g[u])
    {
        if(v == dad) continue;
        dfs1(v, u); siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tup)
{
    top[u] = tup;
    if(son[u]) dfs2(son[u], tup);
    for(int v : g[u])
    {
        if(v == son[u] || v == faz[u])
        continue; dfs2(v, v);
    }
}
int LCA(int u, int v)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] > dep[top[v]])
        u = faz[top[u]];
        else
        v = faz[top[v]];
    }
    return dep[u] < dep[v] ? u : v;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    cnt = n;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);    
        fa[i] = i;
    } 
    for(int i = 1; i <= n; i++)
    scanf("%lld", &b[i]);
    
    for(int i = 1; i <= m; i++)
    {
        int u, v; ll w;
        scanf("%d%d%lld", &u, &v, &w);
        e[i] = edge{u, v, w};
    }
    //虚拟节点处理特殊点
    for(int i = 1; i <= q; i++)
    {
        int u; scanf("%d", &u);
        e[++m] = edge{u, n+1, cjb};
    } 
    ++cnt;
    
    klskr(); dfs1(cnt, 0); dfs2(cnt, cnt);
    
    ll now = b[a[1]]; //当前身上携带的黄金
    if(now < 0)
    {
        now = 0;
        printf("0\n");
    }
    for(int i = 2; i <= n; i++)
    {
        int u = a[i-1], v = a[i];
        ll res = dis[LCA(u, v)];
        if(b[v] > 0)//买入交易直接全拿下买，如果后来发现买多了就 智慧核心 假装没买
        {
            now = min(now, res) + b[v];
        }
        else
        {
            res = min(now, res);
            ll fk = min(res, abs(b[v]));
            printf("%lld\n", fk);
            now = res - min(res, abs(b[v]));
        }
    }
    
    return 0;
}
Kruskal重构树
https://ve1bae.github.io/2022/09/04/kruskal重构树/
本文作者
Veibae
发布于
2022年9月4日
更新于
2022年11月8日
许可协议
CC BY-NC-SA 4.0
署名-非商业性使用-相同方式共享 4.0 国际。

更新于：2022年11月8日

图论

评论