到学校了，网络今天下午才好。在家的时候就看了匹配的算法。匹配这块最常用的应该是两个算法，一个是无权二分图的最大匹配。另一个则是带权图的最大（最小）匹配的KM算法。这篇先说前者...
参考文章：
稍微解释一下，这个算法的核心就是寻找增广路。举个例子说，我们把当前已经匹配的边赋值1，其他的边赋值0，那么增广路就是0101...10这样的一条路，0的个数比1要多一个。如果0->1,1->0，那么匹配数就会增加1，于是当找不到增广路的时候，当前就是最大匹配。
至于实现，以前上离散数学的时候就学过这个算法。当时感觉好难实现。看了代码之后才发现挺简单的（比什么后缀数组什么的简单多了...)。关键就是一个核心的递归。即0也是一条增广路，或者01....省略号也代表一条增广路。那么就找到了一条增广路。把编码改成10....即可。
练习的话可以参考hdu分类的assignment problem:
阅读(1039) | 评论(1) | 转发(0) |
