(HDUACM2010版-13)二分匹配及其应用PPT学习课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,*,ACM程序设计,杭州电子科技大学 刘春英,acm,1,2,2,2,今天，,你开始 了吗？,复习,2,3,本周双星,（1,2,）：,zhanlang,2,4,第十三讲,二分图及其应用,（Bipartite Graph）,2,5,主要内容,什么是二分图,二分图的最大匹配,匈牙利算法,二分图的最小顶点覆盖,DAG图的最小路径覆盖,二分图的最大独立集,处理技巧,2,6,什么是二分图？,如果一个图的顶点可以分为两个集合X和Y，图的所有边一定是有一个顶点属于集合X，另一个顶点属于集合Y，则称该图为,“,二分图,”,（Bipartite Graph）,2,7,例1：婚配问题,男,女,2,8,二分图的最大匹配,在二分图的应用中，最常见的就是,最大匹配,问题，很多其他的问题都可以通过转化为匹配问题来解决。,2,9,如何求二分图的最大匹配呢？,2,10,经典算法：,匈牙利算法,2,11,匈牙利算法(求二分图最大匹配),谈匈牙利算法自然避不开Hall定理,Hall定理：对于二分图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有：|T(A)|=|A|,2,12,图示（1）：,男1,男2,女1,女2,女3,返回,2,13,图示（2）：,男1,男2,女1,女2,女3,返回,X0=男2,V1=男2,V2=,T(V1)=女1,Y=女1,V1=男2，男1,V2=女1,Y=女2,MME(P),(其中，P是从x0 y的可增广道路),2,14,匈牙利算法,基本步骤,：,1任给初始匹配M；,2若,X已饱和,则结束，,否则,进行第3步；,3在X中找到一个非饱和顶点x0，,作V1 x0,V2 ；,4若T(V1)=V2则因为无法匹配而停止，否则任选一点y T(V1)V2；,5若y已饱和则转6，否则做一条从x0 y的可增广道路P，MME(P)，转2；,6由于y已饱和，所以M中有一条边(y,z)，作 V1 V1 z,V2 V2 y，转4；,2,15,图示,（3）：,男1,男2,女1,女2,返回,X0=男2,V1=男2,V2=,T(V1)=女1,T(V1)!=V2,Y=女1,V1=男2，男1,V2=女1,T(V1)=V2,2,16,NOTE:,真正求二分图的最大匹配的题目很少，往往做一些简单的变化，比如,2,17,变种1：二分图的最小顶点覆盖,在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是,二分图的,“,最小顶点覆盖,”,。,2,18,实 例 分 析,2,19,例2：严禁早恋，违者开除！,男生,女生,2,20,例3：HDOJ_1150 任务安排,有两台机器A和B以及N个需要运行的任务。每台机器有M种不同的模式，而每个任务都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式ai,如果它在机器B上运行，则机器A需要设置为模式bi。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。,ACM/ICPC Beijing 2002,2,21,图示：,结论：,二分图的最小顶点覆盖数=,二分图的最大匹配数,a0,a1,a2,a3,a4,b0,b1,b2,b3,b4,2,22,特别说明:,此题需要注意的一点，具体参见：,Air Raid,有一个城镇，它的所有街道都是单行的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。,你的任务是编写程序求最小数量的伞兵，这些伞兵可以访问（visit）所有的路口。对于伞兵的起始降落点不做限制。,2,25,Input:,433 41 32 3,Output:,2,样本数据：,2,26,“,空袭,”,示意图,1,2,3,4,4,3,2,1,1,3,2,4,2,27,结论：,DAG图的最小路径覆盖数=,节点数（n）-最大匹配数（m）,关键：,求二分图的最大匹配数,2,28,变种3:二分图的最大独立集,HDOJ_1068 Girls and Boys,大学二年级的时候，一些同学开始研究男女同学之间的缘分。研究者试图找出没有缘分同学的最大集。程序的结果就是要输出这个集合中学生的数量。,2,29,样本数据：,输入：,70:(3)4 5 61:(2)4 62:(0)3:(0)4:(2)0 15:(1)06:(2)0 1,输出：,5,2,30,0,0,1,5,4,3,2,6,5,4,3,2,1,6,“,Girls and Boys,”,示意图,2,31,结论：,二分图的最大独立集数=,节点数（n）,最大匹配数（m）,关键：,求二分图的最大匹配数,2,32,Any Questions?,2,33,相关练习,201003ACM程序设计在线作业（13）,二分匹配,2,34,附:参考源码(HDOJ-1150),/*hdoj_1150匈牙利算法 月下版*/#include#include#includeusing namespace std;bool mark1100,mark2100;int list100;int n,m,edge,num;vector v;bool dfs(int to)register int i,point,s=listto;for(i=0;ivs.size();i+)point=vsi;if(!mark2point)continue;mark2point=false;if(listpoint=-1|dfs(point)listpoint=s;return true;return false;void Solve()int i,j,point;bool flog=false;memset(mark1,true,sizeof(mark1);memset(list,-1,sizeof(list);num=0;for(i=0;in;i+)for(j=0;jn)if(n=0)break;v.clear();v.resize(n);cin m edge;for(i=0;i j s d;vs.push_back(d);Solve();return 0;,2,35,Welcome to HDOJ,Thank,You,