ACM讲课之二分图匹配(匈牙利算法)-PPT.ppt

ACM讲课之二分图匹配(匈牙利算法)什么是二分图？在离散数学中，我们都学过偶图，而偶图就是二分图。二分图二分图：给你一个图，它的顶点可以分为两个集合，集合V1和V2，所有关联边的一个顶点在V1中，另一个顶点则在V2中。v1v2v3v4v5v1v2v3v4 二分图 非二分图2 什么是二分图匹配？二分图匹配二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。v1v2v3v4v5v1v2v3v4v5 匹配1 匹配23二分图的最大匹配最大匹配最大匹配：图中包含边数最多的匹配称为图的最大匹配。今天我要讲的是无权二分图的最大匹配问题，采用匈牙利算法。4匈牙利算法必备知识：1.盖点盖点：有被M中的边关联到的节点，未盖点未盖点则相反。2.增广路径增广路径：若二分图中有一条路径p，其起始点和结束点都是未盖点，其间属于M的边和不属于M的边交替出现，则称路径p是一条关于M的增广路径。匈牙利算法匈牙利算法：计算二分图最大匹配就是应用增广路径的概念，每次寻找一条关于M的增广路径p，通过M和增广路径进行异或，使得M中的匹配数增加1。以此类推，直至二分图中不存在关于M的增广路径为止。此时得到匹配M就是图G的一个最大匹配。注：M为一个边集，M就是二分图的匹配5结合增广路径的定义和下图所示，我们可以理解以下结论：1.增广路径的长度必定为奇数，第一条边和最后一条边都不属于 M。2.将 M 和增广路径进行异或操作（去同存异）可以得到一个更大的匹配 M。3.M 比 M 的匹配数多 1。4.M 为 G 的最大匹配当且仅当不存在 M 的增广路径。核心核心：判断当前结点为起点的增广路径是否存在判断当前结点为起点的增广路径是否存在。6poj1274题目大意题目大意：有N头奶牛，M个产奶的棚子，每头奶牛都有自己想去产奶的几个棚子，问可以产生的最大匹配数。数据：Sample Input5 5 N M2 2 5 第一头：t m2 m53 2 3 4 第二头：t m2 m3 m42 1 5 第三头：.3 1 2 5 第四头：.1 2 第五头：.Sample Output47大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点8解题思路解题思路：将奶牛看成N集合，棚子看成M集合1,对于N集合中一个未匹配的节点i,寻找它的每条关联边,如果它的边上的另一个节点j还没匹配则表明找到了一个匹配,直接转步骤4;2,假如节点i它边上的另一个节点j已经匹配,那么就转向跟j匹配的节点，也就是它的前驱,假设是prej,然后再对prej重复1,2的步骤,即寻找增广路径寻找增广路径.3,假如我们在1,2步过程中找到一条增广路,那么修改各自对应的匹配点,转步骤4,若无增广路,则退出.4,匹配数+1;923455432112345543211102345543211i=1 时：Pre2=1;112345543211123i=2 时：Pre5=1;Pre2=2;1223455432111i=3时：Pre1=3;132345543211i=4时：Pre3=2;Pre2=1;Pre5=3;Pre1=4;14