二分图最大匹配 (2)

1、二分图最大匹配 2006 12 191引例N 项工作分配给N 个人去做，以知每个人可以完成的工作列表，其中每人只能从事一项工作，每项工作只能由一人来完成。问怎样才能完成尽可能多的工作？ 工作列表：A： x yB： y zC ： x其中ABC为工作人员；xyz为工作。2相关定义设G=V, E是一个无向图。如顶点集V可分割为两个不相交的子集X和Y，并且图中每条边连接的两个顶点都属于两个不同的子集，则称图G为二分图。给定一个二分图G，在G中若干边组成的集合M中，任意两条边都不与同一个顶点相连，则称M是G的一个匹配。其中边数最多的匹配叫做二分图的最大匹配。3azyxcbazyxcb普通匹配 (a, x

2、), (b, y) azyxcb最大匹配： (a, y), (b, z), (c, x) 4求二分图的最大匹配网络流算法：匈牙利算法：寻找关于当前匹配的增广路径，然后沿增广路径进行增广，将得到一个更大的匹配，重复这一过程，直到找不到增广路径时停止。5增广路径关于M的增广路径：连接X和Y中两个未匹配顶点的的路径，并且该路径上属于M和不属于M的边交替出现。增广路径的长度为奇数，第一条边和最后一条边都不属于M。匹配M上去掉增广路径上原属于M的边，加入增广路径上原不输入M的边，将得到一个更大的匹配。重复以上过程，当不存在增广路径时，将得到一个最大匹配。6azyxcb原图azyxcb当前匹 配 Mazy

3、xcb增广路径：c, x, a, y, b, zazyxcb增广后的匹配：M M7匈牙利算法的具体实现Boolean型数组 cu, v表示原图中u到v之间是否有边。Boolean型数组 xk ( yk ) 表示当前寻找增广路径时X ( Y ) 集合中k点是否访问过。Linkk ： 如果Linkk0 则边 ( Linkk, k ) 属于当前匹配8procedure mainwork; 主过程 ans:=0; 匹配的边数 fillchar( link, sizeof(link), 0 ); 当前匹配没有边 for k:=1 to n do 为X中k点寻找匹配边 fillchar(x, sizeof

4、(x), false); fillchar(y, sizeof(y), false); 开始XY都未访问 if find(k) then inc(ans); 找到合适的边 writeln(ans); for k:=1 to n do if linkk0 then writeln(linkk, ,k); 输出匹配 9function find(v:integer):boolean; 寻找增广路径 if xv then exit(false); 已经访问过v点 xv:=true; for i:=1 to n do 寻找没访问过 if cv,i and not yi then 的Y中的点 yi:=t

5、rue; if (linki=0) or find(linki) linki:=v; exit(true); 找到增广路径 exit(false); 没找到增广路径 10引例分析若a可以完成x, y两项工作，则连 (a, x), (a, y) 两条边最后求该图的最大匹配。azyxcb11超级英雄现在电视台有一种节目叫做超级英雄，大概流程就是每位选手到台上回答主持人的若干个问题，然后根据回答问题的多少获得不同数目的奖品或奖金主持人总是准备了若干道题目，只有当选手正确回答一道题目后，才能进入下一题，否则就被淘汰为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等12这里，我们把规则稍微改变一下假设主持人一共有道题目，选手有种不同的”锦囊妙计”主持人规定，每道题目都可以从两种锦囊妙计中选择一种，而每种锦囊妙计只能使用一次我们又假设一道题目用了他允许的锦囊妙计后，就一定能够正确回答，顺利进入下一题现在我来到