计算二分图的算法有网络流算法和匈牙利算法（目前就知道这两种），其中匈牙利算法是比较巧妙的，具体过程如下（转自组合数学）：
令g=（x,*,y）是一个二分图，其中x={x1,x2
},y={y1,y2,.}.令m为g中的任意匹配。
1。将x的所有不与m的边关联的顶点表上￥，并称所有的顶点为未扫描的。转到2。
2。如果在上一步没有新的标记加到x的顶点上，则停，否则 ，转3
3。当存在x被标记但未被扫描的顶点时，选择一个被标记但未被扫描的x的顶点，比如xi，用（xi）标
记y 的所有顶点，这些顶点被不属于m且尚未标记的边连到xi。
现在顶点xi 是被扫描的。如果不存在被标记但未被扫描的顶点，转4。
4。如果在步骤3没有新的标记被标记到y的顶点上，则停，否则转5。
5。当存在y被标记但未被扫描的顶点时。选择y的一个被标记但未被扫描的顶点，比如yj，
用（yj）标记x的顶点，这些顶点被属于m且尚未标记的边连到yj。现在，顶点yj是被扫描的。
如果不存在被标记但未被扫描的顶点则转道2。
由于每一个顶点最多被标记一次且由于每一个顶点最多被扫描一次，本匹配算法在有限步内终止。
匈牙利算法思想:
今天刚看了二分匹配..以前的没怎么好好想过，今天看了下，其实很简单..就是不断找增广路
过程...有x,y两个集合，对x这个集合每个点遍历一遍，遍历当前点时，如果y中有个未匹配的点
，直接跳出,ans++,如果在y中所有和x的点都匹配过，则对这些点再找，如果有其他的路，则
更新，ans++，如果没，则把当前的点置为匹配的点，ans不变..x++;
相关题目:
http://acm.hdu.edu.cn/showproblem.php?pid=1151http://acm.hdu.edu.cn/showproblem.php?pid=1068http://acm.hdu.edu.cn/showproblem.php?pid=1150http://acm.hdu.edu.cn/showproblem.php?pid=1281http://acm.hdu.edu.cn/showproblem.php?pid=1498http://acm.hdu.edu.cn/showproblem.php?pid=1528http://acm.hdu.edu.cn/showproblem.php?pid=1507相关知识:
二分图的最小顶点覆盖=二分图的最大匹配数
二分图的最大独立集=顶点数-二分图的最大匹配数
二分图的最小路径覆盖=顶点数-二分图的最大匹配数
posted on 2008-07-31 15:56
小果子 阅读(688)
评论(0) 编辑 收藏 引用