2023.7.19 学习笔记

常规
1

最小生成树

前置：

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

优化 :

  • 按秩合并 : 我们可以将节点较少或深度较小的树连到另一棵
  • 路径压缩 : 查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询。

复杂度 : O(n \times alpha(n))

拓展 : 带权并查集

我们还可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。

eg1 :

维护一个 n 长序列, 原都为可用

  • 标记某个元素是不可以
  • 查询某个元素位置后第一个可用的元素

eg2 : [ABC238E] Range Sums

solution :

我们知道了 sum[r] - sum[l - 1] = k

故我们知道了 sum[l - 1] 就能计算出 sum[r]

故把每一个 l - 1 和 r 放在一个并查集中,

根据 sum[0] = 0 我们就能知道 sum[n]

(前提是 0 和 n 在一个并查集)

正题 :

kruskal

  • 思想 : 贪心
  1. 把所有的边按边权排序
  2. 以此枚举每条边, 判断是否不连通
  3. 把这条边加入最小生成树， 合并两并查集

复杂度 : O (m \log (m))

kruskal \text{重构树}

在跑 kruskal 的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。

首先新建 n 个集合，每个集合恰有一个节点，点权为 $0$。

每一次加边会合并两个集合，我们可以新建一个点，点权为加入边的边权，同时将两个集合的根节点分别设为新建点的左儿子和右儿子。然后我们将两个集合和新建点合并成一个集合。将新建点设为根。

不难发现，在进行 n - 1 轮之后我们得到了一棵恰有 n 个叶子的二叉树，同时每个非叶子节点恰好有两个儿子。这棵树就叫 kruskal 重构树。

性质 :

  • 原图中两个点之间的所有简单路径上最大边权的最小值

= 最小生成树上两个点之间的简单路径上的最大值

= kruskal 重构树上两点之间的 LCA 的权值。

  • 从 i 出发, 经过的每一条边都不超过 k , 能到达哪些
    点

则在重构树上, 找到最后一个 \le k 的 i 的祖先

它的所有子树内的所有节点都可以到达

fa_in_tree[find(x)] = ++ tot;
fa_in_tree[find(y)] = tot;
val[tot] = e[i].val;

prim

它死了

在多点少边时略快于 kruskal

复杂度 : O ((n + m) \log (m))

eg1 : [NOIP2013 提高组] 货车运输

solution :

  • 首先重新建图
  • 构造出最大生成树
  • 然后在最大生成树上求 LCA 来回答询问

eg2 :

一个国家有n个城市, 若干个城市之间有电话线连接,
先要增加 m 条电话线使所有城市直接或间接与其他所有城市相连.

solution:

  • 先把已知的被电话线相连两个点加入一个连通块(缩点)
  • 跑 kruskal

eg3 : [USACO08OCT] Watering Hole G

solution :

  • 建一个超级源点 把每个点与那个超级源点相连, 边权为打井的话费
  • 跑 kruskal

eg4 : [USACO08NOV] Cheering up the Cow G

solution :

  • 把 i → j 边权改为 w_{i, j} + c_j

  • 把 j → i 边权改为 w_{i, j} + c_i

  • 合并得 i - j 边权为 2 \cdot w_{i, j} + c_i + c_j

  • 跑 kruskal

eg4. [NOI2018] 归程

solution :

  • 如果我们以海拔为第一关键字对边进行从大到小的排序，然后修建
    kruskal 重构树，这样就弄出了一颗以海拔为关键字的小根堆。然后对于每一棵子树，如果询问中的水位线是低于子树的根节点的，那么此时这棵子树中的所有叶子结点都是连通的。放到题中就是说这颗子树中任选一个点出发，到子树中的其它点都不需要花费。

  • 然后我们假设对于当前询问，我们找到了一个子树的根节点 u ，满足
    d[u] > p 且 d[fa[u]] \le p 且出发点 v 在子树中，这时从 v 出发可以直接抵达子树中的任意一个叶子结点。因此我们需要从众多叶子节点中选出一个距离 1 号点花费最小的。

  • 然后再捋一捋思路。我们首先要求出每个点到 1 号点的最小花费，这个直接 dijstra\ + 最短路预处理。然后是要建出 kruskal 重构树，再然后维护以每个点作为根节点时子树中距离 1 号点的最小花费，这个建完树后一个简单的 dfs 搞定。最后是如何找到点 u ，这时我们要让一个重要的算法登场：倍增算法。直接加上点权 > p 的限制在树上倍增即可。

eg4 : Labyrinth

solution :

由于宽度的变大， 会导致某些边无法通过，在图上就表示为边的断裂

故我们要保证在断开边时形成的两个连通块中

  • 其中一个连通块内的所有糖果被吃完
  • 且我们在另一个连通块

而在重构树体现于一棵树被砍成两颗子树

我们设 dp[x] 为吃 x 这个连通块所允许的最小初始宽度

那么若断开前先吃完了子树 u:

dp[x] + \sum c_u \le w

dp[x] + \sum c_u \le dp[v]

可得状态转移方程:

dp[x] = max(min(w, dp[v]) - treesum[u],min(w, dp[u]) - treesum[v])
treesum[x] = treesum[u] + treesum[v];

小组成员 : 邵品渊，邵品砚，蒋佳成，顾天泽，马天翔，陈继禹

1 个赞
2

膜拜