生成树小总结

无向图最小生成树

Prim算法

这个实现做的非常不好,需要改进。对付稠密图,Prim更胜Kruskal一筹。

Kruskal算法

[这个实现等待填坑]

Borůvka算法

[这个实现等待填坑]

有向图最小生成树(最小树形图)

复杂度O(V * E),以下代码仅存储边,而且会对存储结构发生破坏,请注意。实现来源于国立台湾师范大学。我对这份代码进行了更加详细的注释。

适用于固定了生成树的根的情形

适用于生成树的根无法确定的情形

引用自GentieH,谢谢。

建立虚拟节点x,令x连所有的点,权值为所有边权的总和+1,求得最后结果减去该值即可,由于虚拟节点的存在,不会显式地出现孤立点,这时通过判断如果存在多与1个节点的pre为root,则说明无解。如果需要求出根节点,由于之前将x与图中的点连边时,我们按顺序连的话,考虑到可以用边去标识点,对于每一个终点v,如果它的pre为root,则标记这条边who,在求结果时,让who-E即可。

要求输出方案的情形

CF240E

 

次小生成树

[Pending Session]

增量最小生成树

[Pending Session]

最小瓶颈生成树

[Pending Session]

生成树问题混杂其他类型问题

二分图小总结

知识

二分图大讲堂——彻底搞定最大匹配数(最小覆盖数)、最大独立数、最小路径覆盖、带权最优匹配

这一篇已经足够了。

模板

匈牙利算法,复杂度O(V*E),使用“vector邻接表”存储图。MAXN为单边最大节点数量,需要按照题目要求调整,INF是理论最大值不够的话按照题目要求调整。左手边和右手边的节点序号从0开始,建图前,执行init,并正确配置nx(左手边节点数量)和ny(右手边节点数量),BGM_H()返回最大匹配数。

Hopcroft-Karp算法,复杂度O(sqrt(V) * E),适配方法同匈牙利算法模板,调用是BGM_HK(),不适合活用。

配套练习

二分图・ア

POJ 1274 The Perfect Stall(教学题)
POJ 2446 Chessboard(骨牌模型转化)
POJ 2594 Treasure Exploration(允许相交的最小路径覆盖)
POJ 1325 Machine Schedule(适当建图,最小点覆盖问题)
POJ 1469 COURSES(教学题)
HDU 3225 Flowers Placement(匈牙利算法在DFS中的剪枝作用)

 

HDU 3225 Flowers Placement

题意

求第k小的二分图最大匹配方案。

思路

这个题需要我们活用匈牙利算法了。首先正常地建图,运行一次匈牙利算法,这样初步得到了一种最大匹配样态。

接下来,我们使用DFS,从第一束花开始,从小到大挨个枚举这一位放什么,对于每一次枚举,首先要检查在当前已经有的匹配里面是不是这种花已经被匹配过了,如果是的话要解除这一匹配,接下来我们要把这一位在二分图中的匹配指向被枚举的那种花,如果被枚举的那种花原来是指向当前位置的,我们可以直接继续搜索,因为二分图可以继续有机会保持匹配,否则的话我们要以被枚举的那种花原来的东家为起点,进行一次增广路搜索(即匈牙利算法中的一环),如果没有搜索到增广路,说明这样下去也不可能出现最大匹配,可以剪枝了。

注意,如果增广路搜索失败,要把启动搜索之前的那些临时性修改复原,如果增广路搜索成功,那些修改就可以保留了。在增广路搜索过程中,注意不可以让增广路搜索修改当前DFS深度之前的已经固定了的节点。

当深度到达n时,就可以知道当前是一种合法的最大匹配样态,我们可以给计数器+1,当计数器到达k时,中断DFS过程,纪录回溯路径就是答案了。

这种方法可能有一些难以理解,其实只要把增广路过程给当成一种把当前的图给变成匹配了的图的一种“尝试修复”的过程就好了,如果尝试成功,说明以当前图的形态,还有机会出现最大匹配,如果尝试适失败,说明当前图的形态没有前途,不用再深入考虑了。

代码

 

POJ 1469 COURSES

题意

判定给出的二分图是否存在完备匹配。

思路

按照题目要求直接建立二分路,之后运行最大匹配算法,出答案。

代码

使用了匈牙利算法。

 

POJ 1325 Machine Schedule

题意

给你两台机器和k个工件,要你设计最优调度方案。对于每个机器,一共有0 ~ n-1(或者是m-1)这n(或者是m)个状态,初始状态都是0。对于每个工件,要么在x号状态下加工,要么在y号状态下加工。你要给出两台机器一共最少要切换多少次状态,才可以加工完全部工件。

思路

这个题对于建图是很讲究的,第一眼看上去很有二分图的意思。但是如果你这么建图:一边是0~max(m,n)这些状态(因为无论是两台还是一台,其实都是一样的,因为机器运转的时间是无限的,理论上讲就算只给一个机器,也能完成任务,而且和两台机器所需要的切换次数一样),另一边是0~k这些工件,每一个工件都和他可以被加工的状态连上一条边。

但是这么建图并不能解决问题,首先,只要工件可以在0状态加工,就可以看成不存在了,因为机器无需切换状态就可以加工好,这样,我们在图中所有与0状态相连的点,和0状态本身都要去掉。其次,现在我们规约好的问题已经变成了:在一边的图中选出尽可能少的点,使得这些点的所连接的点可以覆盖对面全部的点。这是典型的“最小支配集”问题。最小支配集问题目前还是NP困难问题。所以此路已经不通了。

我们只好换一种思路,我们发现,如果把一个工件可以加工的两个状态连接起来,建立二分图之后。在这个图上,图的两边分别是A机器和B机器,图上的每一条边代表一个工件,我们要求的东西就变成了选出最少的点,使得所引出的边的集合中包含了全部的边,也就是“最小点覆盖问题”。二分图的最大匹配数等于最小覆盖数。问题可做了。

代码

使用了匈牙利算法。

 

POJ 2594 Treasure Exploration

题意

给出一个DAG(有向,没有环的图),现在要你选出尽可能少的几条路径,使得只要把你选出来的路径都走了一遍,就可以保证你已经走过的图中的每一个节点。注意,路径与路径之间,可以有公共点(即允许路径相交)。

思路

典型的“最小路径覆盖”问题。在这里直接给出此类问题的解法:

有向无环图最小不相交路径覆盖

       定义:用最少的不相交路径覆盖所有顶点。

       定理:把原图中的每个点V拆成Vx和Vy,如果有一条有向边A->B,那么就加边Ax-By。这样就得到了一个二分图,最小路径覆盖=原图的节点数-新图最大匹配。

       简单证明:一开始每个点都独立的为一条路径,总共有n条不相交路径。我们每次在二分图里加一条边就相当于把两条路径合成了一条路径,因为路径之间不能有公共点,所以加的边之间也不能有公共点,这就是匹配的定义。所以有:最小路径覆盖=原图的节点数-新图最大匹配。

 

有向无环图最小可相交路径覆盖

       定义:用最小的可相交路径覆盖所有顶点。

       算法:先用floyd求出原图的传递闭包,即如果a到b有路,那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。

 

所谓传递闭包(Transitive Closure)就是指把原图里面所有能直接间接联通的点之间都给连上边(如果有联通的方向限制,这个方向也要保留)之后形成的图,也就是说只要在传递闭包中存在A->B,就一定可以在原图中找到一条从A到B的路径。求传递闭包使用Warshall算法,最简单的实现就是借助邻接矩阵了(下图直接截自离散数学课件):

QQ20150829-1@2x

代码

以下实现使用了Hopcraft-Karp算法和Warshall算法。

 

POJ 2446 Chessboard

题意

给出一个M*N大小的棋盘(M,N都非常小),棋盘上戳了几个洞,然后问你有没有可能用若干张1*2的骨牌,横着或者竖着填满整个棋盘,有洞的地方是不可以放置骨牌的。

思路

因为骨牌是1*2的,如果我们把整个棋盘看成一个图,每个没洞的地方都是一个节点,在棋盘上只要相邻(上下左右四联通)就可以看成两个节点有一条边相连,这样我们就可以发现,每一块骨牌正好就是图上的一条边。所以我们就把问题转化为了:给出一个图,要你用选出尽可能少的边,使得图上的每一个顶点都是选出的边中的某一条的端末,也就是“最小边覆盖”问题。

最小边覆盖=图中点的个数-最大匹配数=最大独立集

所以接下来的事情就很简单,按着上面的说法建图,然后运行一次最大匹配算法,之后作个差就搞定了。

还要注意一点,本题数据给出的形式可能和预想的不一样,挖洞的点是横坐标在前,纵坐标在后,如果WA,不妨检查一下是不是输入的时候做反了。

代码

本实现使用了匈牙利算法。

 

POJ 1274 The Perfect Stall

题意

求二分图最大匹配。

思路

教学题,只要使用了二分图/网络流就可以通过。在这里我强行使用了Hopcroft-Karp Algorithm,因为看了很长时间自己也很难理解,决定抄一遍别人的代码仔细领悟。核心部分我加了好多注释帮助理解。

代码

 

HDU 1394 Minimum Inversion Number

题意

求环形数组的最小逆序数。

思路

如何求逆序对请参考hdu 1394 求循环串的最小逆序数 暴力法 线段树 归并排序3种方法(hnust_xiehonghao)

本题使用暴力方法也可以通过,但前提是需要知道一个结论:如果是0到n的排列,那么如果把第一个数放到最后,对于这个数列,逆序数是减少a[i],而增加n-1-a[i]的

代码(线段树优化方法)

 

HDU 1698 Just a Hook

题意

给出一个数列,每次操作更新一段的值使它们全部为给定值,问你历经N次操作之后,数列所有数加和是多少。

思路

典型的线段树加上懒惰标记来实现区间更新。因为好久没写线段树,拿这个题重温一下。

懒惰标记的工作原理可以参照:ZOJ 3686 A Simple Tree Problem

代码

 

Scroll to top