kkogoro

最小生成树必经边问题
最小生成树必经边十分感谢@zbww大佬的帮助题意给定 $n$ 个点, $m$ 条边的无向图,求最小生成树的必经边。...
扫描右侧二维码阅读全文
14
2019/03

最小生成树必经边问题

最小生成树必经边

十分感谢@zbww大佬的帮助

题意

给定 $n$ 个点, $m$ 条边的无向图,求最小生成树的必经边。

必经边的定义为该图的任意一种最小生成树中都存在该边。

Subtask

(1)点少的稠密图

给定的图为 $n\leq 3000$ 的完全图

(2)点数边数同阶

$n\leq 10^{5}$ , $m\leq 10^{5}$

题解

一些性质

  • 我们对原图求出一颗最小生成树之后,必经边一定是在这颗最小生成树上的
  • 对于任意一条边权为 $w​$ 的非树边 $(u,v)​$ ,在最小生成树上 $u,v​$ 两点之间的路径上不存在边权大于 $w​$ 的边(否则肯定可以用这条非树边替代那条树边得到更小的生成树)
  • 最小生成树上一条边权为 $w$ 的边 $e$ 不是必经边当且仅当存在一条非树边 $(u,v)$ 的权值等于 $w$ 并且 $e$ 在最小生成树上 $u,v$ 两点之间的路径上

一些操作

  • 稀疏图使用Kruskal求解最小生成树,稠密图使用Prim求解最小生成树
  • 可以离线的跟路径覆盖有关问题可以使用差分来解决(如果是对边的覆盖,每条边使用它连接的深处的节点作为它的标准)

Subtask1

先用Prim做一遍最小生成树并标记所有树边复杂度 $O(n^{2})$ ,现在我们只需要考虑边权在树边边权中出现过的边即可,可以对于树上每一种权值预处理出所有同权值的非树边,这里使用平衡树实现 $O(n^{2}\log n)$ (注意这个 $\log$ 很小的),使用hash实现 $O(n^{2})$ ,然后对于每种权值做一次树上路径覆盖的差分然后dfs一次看当前边有没有被同权值的边覆盖过

总时间复杂度 $O(n^{2})$ 或 $O(n^{2}\log n)$

Subtask2

方法1

先用Kruskal做一遍最小生成树,并对最小生成树进行倍增或树剖预处理(用于求LCA),将所有权值里离散化(也可不必)。

对于每条非树边 $(u,v)$ ,设其权值为 $w$ ,我们在最小生成树上 $u,v$ 两点分别打上一个“加入 $w$ 权值”的标记,而在 $LCA(u,v)$ 处打上两个 “删除 $w​$ 权值 ”的标记,每个点处的标记使用vector存储。

对于所有非树边都这样处理后进行一次dfs统计答案:我们维护一个记录某种边权的边有多少个的全局桶(如果一开始没离散化可以使用map),dfs进入一个点时记录这个点对应的边(连接它和他父亲的边)的那个桶内边的个数 $a$ ,dfs完一个点的所有孩子回溯到这个点时,将它的所有增删标记对应的加在桶(或map)上,比如“删除 $w$ 权值 ”就在 $w$ 对应桶减 $1$ ,把标记都处理完之后看这个点对应的边的边权的桶内记录值 $b$ ,如果 $b-a$ 大于 $0$ 就说明这条边被同权非树边覆盖过,就不是必经边。这样处理完之后总的复杂度 $O(m\log n)$

但实际上上述标记也可以用线段树合并来轻松维护,复杂度是一样的(离散化后)

差分是根据没进入一个点之前它子树内的信息没被统计,回溯到这个点后这个点内的信息都被统计,但是全局桶内保存了跟他同父的其他孩子的子树内的值,需要减去

方法2

先用Kruskal做一遍最小生成树,并对最小生成树进行树剖预处理。

维护一个dfs序序列。

对于每条非树边 $(u,v)$ ,设其权值为 $w$ ,我们在最小生成树上 $u,v$ 两点之间的路径上进行树链剖分的跳跃时如果有一个整段的两个端点对应dfs序 $a,b$ ,则存下一个三元组 $(a,b,w)$ ,这表示我们稍后在dfs序上 $a$ 处加入一个权值 $w$ ,在 $b+1$ 处减去一个权值 $w$ ,这样把所有边都处理完之后我们会总共得到 $m\log n$ 个这样的三元组,之后我们从 $1$ 到 $n$ 遍历标记数组用桶维护权值个数即可 $O(m\log n)$ ,要注意lca处不应该存在标记

但实际上方法一和方法二几乎是一样的,只是一个在树上进行,一个将树转化为序列进行

可能还有更优秀的方法……希望您能与我交流一下

Last modification:March 14th, 2019 at 09:26 pm

Leave a Comment