二分匹配

参考文章二分匹配算法理解_K.X的博客-CSDN博客

二分匹配算法是解决两个集合自身间的元素无关系,但两集合间的元素有关系,可将有关系的元素进行匹配,二分匹配可以得到最大匹配数;二分匹配是在一个集合中进行查找,查找不冲突就进行匹配,若出现冲突进行查找增广路,若找到增广路,更新原来的配对关系,具体实现是利用深搜思想查找尝试每一个点,首先从任意一个未被匹配的点u开始,从点u的边中任意选一条边开始配对。如果这个这条边连接的点还没有被配对此时便找到了一条增广路。如果这个点已将被配对了,就尝试进行“连锁反应”。如果尝试成功更新原来的配对关系。用一个match[ ]数组实现,match[ ]数组存储配对关系,初始化match[ ]数组为0,例如当点u与点i配对成功match[i]=u;配对数加1;直到所有的点都尝试完,得到最大匹配数

68c7e90c963143cdbef9c3eb4b491bf6

全部评论

相关推荐

10-15 10:23
门头沟学院 Java
牛可乐的头像真牛:赶紧举报,这公司绝对是诈骗的,等你签约后工作一两个月后根据合同漏洞把你开除,并且要求你赔偿3w培训费,996是为了提前筛选心甘情愿签下合同容易受骗的群体,纯粹面向校招生精心设计的骗局
你见过哪些工贼行为
点赞 评论 收藏
分享
09-25 11:39
已编辑
北京航空航天大学 Java
我的代码出BUG了:@美团@腾讯@字节跳动@阿里巴巴。你们好好看看吧,你们就挂我吧,到时候被人家鸽穿还得录取我
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务