生成树 学习笔记

发表于 | 分类于 | | + s

模板及讲解

最小生成树：在一个图中选择$n-1$条边，使所有点连通且路径总权最小。常用算法是用并查集辅助求解的Kruskal
最小瓶颈路：求一条路径，使得$u−>v$路径上的最大边权最小。可以知道，最小瓶颈路必在最小生成树上，所以用最小生成树求解

最小生成树性质

1切割性质
2回路性质
3相同边权数量相等
4不同边权加入时互相独立
5不产生环的同权值边可以替换边

Kruskal 重构树

定义

在做 Kruskal 的时候，我们将边权转点权，得到$2n-1$个点的树。

构造方法

每次 Kruskal 时，如果当前边是需要的，那么我们建立一个新节点，节点权值为边权，然后从这个点向两边两个集合的并查集代表连边。

性质

1、是一棵树，并且是一个二叉堆
2、原最小生成树两点之间的边权最大值是重构树上两点$\text{LCA}$的权值
3、重构树中代表原最小生成树中的点的节点全是叶子节点，其余节点都代表了一条边的边权。

例题

1、Bzoj 3732

给你$N$个点的无向有边权图，图中有$M$条边，现在有$K$个询问，每个询问的格式是：A B，表示询问从$A$点走到$B$点的所有路径中，最长的边最小值是多少？

最长的边最小值，我们考虑最小生成树。这题明显可以求出最小生成树，然后再在树上倍增 / 树剖求出最长的边。这里可以运用性质2，即原最小生成树两点之间的边权最大值是重构树上两点$\text{LCA}$的权值，那么我们构造出重构树，询问树上两点$\text{LCA}$的权值即为答案。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 30000 + 5, LOGS = 20;

    struct edge {
        int u, v, w;
        bool operator < (const edge &rhs) const {return w < rhs.w;}
    } ed[30000 + 5];

    int n, m, Q, val[MAXN], f[MAXN], idx;
    vector<int > G[MAXN];
    int pre[MAXN][LOGS + 2], dep[MAXN];

    void ins(int u, int v) {G[u].push_back(v);}
    int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
    void dfs(int u, int fa) {
        pre[u][0] = fa, dep[u] = dep[fa] + 1;
        for (int i = 1; i <= LOGS; ++i) pre[u][i] = pre[pre[u][i - 1]][i - 1];
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa) dfs(v, u);
        }
    }
    int LCA(int a, int b) {
        if (dep[a] < dep[b]) swap(a, b);
        for (int i = LOGS; i >= 0; --i) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
        if (a == b) return a;
        for (int i = LOGS; i >= 0; --i) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
        return pre[a][0];
    }

    void clean() {
        ms(val, 0), ms(f, 0);
        ms(pre, 0), ms(dep, 0);
    }
    int solve() {

        clean();
        cin >> n >> m >> Q;
        for (int i = 1; i <= m; ++i) scanf("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].w);
        sort(ed + 1, ed + 1 + m), idx = n;

        // Kruskal
        int tot = 0;
        for (int i = 0; i <= n * 2; ++i) f[i] = i;
        for (int i = 1; i <= m; ++i) {
            int x = find(ed[i].u), y = find(ed[i].v);
            if (x != y) {
                ++idx;
                ins(idx, f[x]), ins(idx, f[y]);
                f[x] = f[y] = idx, val[idx] = ed[i].w;
                ++tot;
                if (tot >= n - 1) break ;
            }
        }

        // LCA
        dfs(idx, 0);

        while (Q--) {
            int x, y; scanf("%d%d", &x, &y);
            printf("%d\n", val[LCA(x, y)]);
        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

常见题型

1、求一个图的最小/大生成树
Q：给出一个图，求出这个图的最小/大生成树
解：见讲解
例题：BZOJ 2429
2、将一个图转为树
Q：给出一个图，图中只有使图连通的最大/小的那几条边有用
解：求最小/大生成树。
例题：NOIP2013 D1 T3
3、求一条路径使得最大边最小
Q：给出一个图，求一条路径使得$a->b$最大边最小(这种题的题面一般带有二分的标志：最大值最小)
解：最小瓶颈路。最大边最小的路径在最小生成树上。
例题：BZOJ 2429
4、最小生成树性质
Q：BZOJ 1016
解：BZOJ 1016
例题：BZOJ 1016
5、最小生成树-倍增 (回路性质)
Q：CF 609E
解：CF 609E
例题：CF 609E

------ 本文结束 ------