首页 > 笔记 > 最小生成树的相关算法

最小生成树的相关算法

学完最小生成树就来学习下它的相关算法吧。。。

在最小生成树的实际应用中我们常常会遇到这一类问题,给你一张无向带权连通图和两个节点u,v让你求u,v之间的一条路径使得u->v路径上最大的边权最小值。这一类问题我们称之为最小瓶颈路问题。

最小瓶颈路

对于最小瓶颈路,要分两种情况讨论,一种是单次询问,一种是多次询问。

1、单次询问

首先,我们从最简单的一个询问来说。我们很容易就能想到对于这一类问题我们可以先求出最小生成树然后在树上执行一次dfs然后就能求出答案了,我想这种应该是最简单的做发复杂度是O(mlogm)能够满足题目的需求。复杂度是不能优化了,但我们可不可以减少一下代码的长度呢,在这里我引用郭华阳在2007年发表的国家集训队论文里的算法。

images

images

images

郭华阳在国家集训队论文里介绍的最小生成树的性质,就是在kruskal算法执行的时候第一次将两个点(或者说两个点的集合)连起来的那条边就是这两点的最小瓶颈路上最大边。(因为kruskal是从小到大依次连边的。)

例题

poj2253 forgger(经典老题)

还有例题luoguP2330

给出题解(用的一种麻烦的方法做的)

还有一种很简单的floyed。。。。

把floyd算法中的‘之和’,’取最小值’改成’最大值’和’取最小值’即可。。。

 

2、多次查询

单个询问非常的简单但是对于多组询问上述解法就没有用武之地了。那这时候我们怎么处理呢?利用lca处理,下面列出算法步骤:

因为要多次访问,所以的话先预处理。因为最短路一定是在最小生成树里的,所以,先求最小生成树,然后把最小生成树改成有根树,有根树中引入层的概念,根据到根节点的距离,分层,如果两个点在同一层,就可以从两边同时找向上层遍历来,因为从两边遍历,所以更省时间,因为层数相同,所以任意两点在向上层遍历的时候必会有祖先相同(此时两点之间就找到了一条路了,而且此路必然就是所求的路了)的情况,此时就找左边点到相同祖先的路的最大边,以及右边的点到相同祖先节点的路的最大边,然后取最大值。。。

例题

uva 11354(只找到这样一道)

次小生产树

另一类相关问题就是次小生成树了。题目的要求就是求出权值第二小的最小生成树的值(若最小有两种方案则值相等),对于次小生成树都有一种暴力做法就是枚举所有不在最小生成树中的边这个能求出答案但是复杂度太高往往无法承受,下面给出一种 O(n^2)算法。

1.求出最小生成树。

2.找出每个点对之间的最大边长 。

3.枚举所有不在最小生成树上的边设(u,v),删除原来u,v之间最大边长,加上这条边的边长,更新答案。

例题

1679 poj

还是很好想的

好了差不多讲完了,其实还有最小树形图(zhuliu算法),最小限制生成树,k度最小生成树(参见2004汪汀国家队论文)。感觉这些都比较难等以后掌握好了在写总结吧。。。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×