8
3
2015
0

二分图匹配之匈牙利算法

http://blog.csdn.net/dark_scope/article/details/8880547

真心推荐这个,非常好懂。二分图匹配的难点不在于算法,而在于应用。

比如XJOI1579这题。我一开始根本想不到二分图匹配,是看了题解之后才想到的。

不存在两个星球i,j,既能从i到达j,又能从j到达i。这说明是有向无环图。

把原图作为二分图的两个点集进行最大匹配。

为什么可以这样呢?

假如i匹配到了j,j匹配到了k,k找不到匹配,就找到了一条可行的路径,找不到匹配的k就是该路径的终点,而终点的个数(点的总数减去匹配的点个数)就是路径的条数。

由于一个点只能被匹配一次,所以不会出现路径相交的情况。由于是最大匹配,所以路径条数最少。

目前我只能理解到这一层,但感觉太妙了。

Category: 算法 | Tags: 二分图 XJOI

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com