计算二分图的算法有网络流算法和匈牙利算法(目前就知道这两种),其中匈牙利算法是比较巧妙的,具体过程如下(转自组合数学):
令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
小果子 阅读(686)
评论(0) 编辑 收藏 引用