大飞同学问我这一题, 图论的东西我是一点都没看过, 直接看了discuss
做这题用了得有十个小时.. 我可是连二分图都不知道是什么..
然后什么是二分图匹配呢

而

最小覆盖数 == 节点数 – 最大匹配数

为什么呢, 数学归纳一下, 匹配数为0时显然 最小覆盖数 == 节点数, 然后有一个二分图匹配就能把两个覆盖路径合二为一, 很简单. 具体的在ufo008ahw这里有所说明
扩展阅读： Matrix67牛有一篇文章介绍了二分图最大匹配的König定理及其证明

求二分图最大匹配用匈牙利算法或者最大流(这个我还没看- -).
有向图转化成二分图很简单, 把每个节点变成两个节点(在二分图两边)一个负责入一个负责出即可

至此我们已经可以解决有向图的最小路径覆盖问题. 允许路径重叠的情况怎么办呢, 明显是要转化成不允许路径重叠的情况来依葫芦画瓢, 想要在求二分图最大匹配的过程中考虑允许重叠的情况我想过.. 没想出来, 难度吹牛逼一样.

怎样转化: 用Floyd求一下传递闭包即可, 这个我想了好久才明白, 我来说明一下
比如有向图G: 1->2->3 4->2->5
解释是: 对于任何的有重复节点的路径, 比如这里的2, 求了传递闭包以后的图就会包含1->3和4->5这两个路径, 实现”跳过去”的走法

Floyd没什么好说的, 关于匈牙利算法(初次接触)的一些细节:

1. 下面这个代码的我是看的这里, 这个数据结构和递归太牛了..做完我整个人都犀利了. 它是只记y指向x不记x指向y, 每次对x搜索可用的y, 而不是记录它们, 整个操作都简单了好多. 原文的注释写的很好
2. 代码中的visited[] 这个验证我列举了各种情况, 是正确的, 有点难度
3. 算法的原理我很清楚了. 但是代码里x和y双重循环, 为什么x和y各循环一遍就ok了我还是没有理解太透彻, 这也是匈牙利算法的精髓吧

代码点下面:
Continue reading →