http://blog.csdn.net/dark_scope/article/details/8880547
真心推荐这个,非常好懂。二分图匹配的难点不在于算法,而在于应用。
比如XJOI1579这题。我一开始根本想不到二分图匹配,是看了题解之后才想到的。
不存在两个星球i,j,既能从i到达j,又能从j到达i。这说明是有向无环图。
把原图作为二分图的两个点集进行最大匹配。
为什么可以这样呢?
假如i匹配到了j,j匹配到了k,k找不到匹配,就找到了一条可行的路径,找不到匹配的k就是该路径的终点,而终点的个数(点的总数减去匹配的点个数)就是路径的条数。
由于一个点只能被匹配一次,所以不会出现路径相交的情况。由于是最大匹配,所以路径条数最少。
目前我只能理解到这一层,但感觉太妙了。