[ACM] POJ 2594 求有向图(允许路径重叠的)最小路径覆盖, Floyd + 匈牙利算法

大飞同学问我这一题, 图论的东西我是一点都没看过, 直接看了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了我还是没有理解太透彻, 这也是匈牙利算法的精髓吧

代码点下面:
Read More

[ACM] POJ 1161 解题报告, 图论, 几何

好繁的一道题.. 看走眼了 1061才是数论题..才发现 思路:

区域看作一个Vertex, 对每个区域BFS求出能到达所有club的和最小值. 复杂度N2
Edge的构造:  一个region周围的点集按顺时针是 {p1, p2, p3 .. pk} 那么 (p1, p2) (p2, p3) … (p(k-1), pk) (pk, p1) 就是它的所有border, 其中任何一条边 (p[j], p[(j+1)%n]) 与也只与另外一个region’ 共享,  而region’ 做取边操作的时候, 这条共享边是颠倒的, 即 (p[(j+1)%n], p[j]) , 所以构造一个二维数组p[][], 上下三角形是对称的, 一对对称的元素就代表了相连的两个区域
club就存在所有靠着它的region内, 在这些region里面此club的步数都是0

细节:

以后这种繁题把变量名起的明白一点.. 多写点注释,  不然容易糊涂, 不太好写函数(其实可以.. 懒)

110行, 跑47ms, 还不错的样子..

Update: 这题数据比较弱, 用floyd简便很多, 因为为BFS准备比较麻烦, floyd直接开个数组全∞了事.. 复杂度N3

代码点下面 (没有任何可读性可言..)
Read More