资源描述
,单击此处编辑母版样式,单击此处编辑幻灯片母版样式,第二层,第三层,第四层,第五层,*,精,*,单击此处编辑母版样式,单击此处编辑幻灯片母版样式,第二层,第三层,第四层,第五层,*,精,*,ACM,程序设计,计算机学院 刘春英,精,1,ACM 程序设计计算机学院 刘春英精1,今天,,请个假,下周调课,(,西安,),精,2,今天,请个假,精2,每周一星(,8,):,05072120,精,3,每周一星(8):05072120精3,第九讲,二分图及其应用,(,Bipartite Graph & Applications,),精,4,第九讲二分图及其应用精4,主要内容,什么是二分图,二分图的最大匹配,匈牙利算法,二分图的最小顶点覆盖,DAG,图的最小路径覆盖,二分图的最大独立集,处理技巧,精,5,主要内容什么是二分图精5,什么是二分图?,如果一个图的顶点可以分为两个集合,X,和,Y,,图的所有边一定是有一个顶点属于集合,X,,另一个顶点属于集合,Y,,则称该图为“二分图”(,Bipartite Graph,),精,6,什么是二分图?如果一个图的顶点可以分为两个集合X和Y,图的所,例:婚配问题,男,女,精,7,例:婚配问题男女精7,二分图的最大匹配,在二分图的应用中,最常见的就是最大匹配问题,很多其他的问题都可以通过转化为匹配问题来解决。,精,8,二分图的最大匹配 在二分图的应用中,最常见的就是最大匹,如何求二分图的最大匹配呢?,精,9,如何求二分图的最大匹配呢?精9,经典算法:,匈牙利算法,精,10,经典算法:匈牙利算法精10,/*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;,精,11,/*hdoj_1150匈牙利算法 月下版 */#incl,匈牙利算法,(,求二分图最大匹配,),谈匈牙利算法自然避不开,Hall,定理,Hall,定理:对于二分图,G,,存在一个匹配,M,,使得,X,的所有顶点关于,M,饱和的充要条件是:对于,X,的任意一个子集,A,,和,A,邻接的点集为,T(A),,恒有:,|T(A)| = |A|,精,12,匈牙利算法(求二分图最大匹配)谈匈牙利算法自然避不开Hall,图示(,1,):,男,1,男,2,女,1,女,2,女,3,返回,精,13,图示(1):男1男2女1女2女3返回精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,的可增广道路,),精,14,图示(2):男1男2女1女2女3返回X0=男2精14,匈牙利算法是基于,Hall,定理中充分性证明的思想,其基本步骤为,:,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,;,精,15,匈牙利算法是基于Hall定理中充分性证明的思想,其基本步骤为,图示(,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,精,16,图示(3):男1男2女1女2返回X0=男2精16,NOTE:,真正求二分图的最大匹配的题目很少,往往做一些简单的变化,比如,精,17,NOTE:真正求二分图的最大匹配的题目很少,往往做一些简单,变种,1,:二分图的最小顶点覆盖,在二分图中求最少的点,让每条边都至少和其中的一个点关联,这就是,“,二分图的,最,小,顶点,覆,盖,”,。,精,18,变种1:二分图的最小顶点覆盖在二分图中求最少的点,让每,实 例 分 析,精,19,实 例 分 析精19,例:严禁早恋,违者开除!,男生,女生,精,20,例:严禁早恋,违者开除!男生女生精20,例:任务安排,有两台机器,A,和,B,以及,N,个需要运行的任务。每台机器有,M,种不同的模式,而每个任务都恰好在一台机器上运行。如果它在机器,A,上运行,则机器,A,需要设置为模式,ai,如果它在机器,B,上运行,则机器,A,需要设置为模式,bi,。每台机器上的任务可以按照任意顺序执行,但是每台机器每转换一次模式需要重启一次。请合理为每个任务安排一台机器并合理安排顺序,使得机器重启次数尽量少。,hdoj_1150,(,LRJ_p331,),ACM/ICPC Beijing 2002,精,21,例:任务安排有两台机器A和B以及N个需要运行的任务。每台机,图示,:,结论:,二分图的最小顶点覆盖数,=,二分图的最大匹配数,a0,a1,a2,a3,a4,b0,b1,b2,b3,b4,精,22,图示:结论:a0a1a2a3a4b0b1b2b3b4精22,特别说明,:,此题需要注意的一点,具体参见:, DAG图的最小路径覆盖用尽量少的不,例:空袭,(,Air Raid,),有一个城镇,它的所有街道都是单行的,并且每条街道都是和两个路口相连。同时已知街道不会形成回路。,你的任务是编写程序求最小数量的伞兵,这些伞兵可以访问(,visit,)所有的路口。对于伞兵的起始降落点不做限制。,hdoj_1151,精,25,例:空袭(Air Raid)精25,Sample input:,433 41 32 3,Output:,2,精,26,Sample input:433 41 32 3O,“,空袭”示意图,1,2,3,4,4,3,2,1,1,3,2,4,精,27,“空袭”示意图123443211324精27,结论:,DAG,图的最小路径覆盖数,=,节点数(,n,),-,最大匹配数(,m,),关键:,求二分图的最大匹配数,精,28,结论:DAG图的最小路径覆盖数=精28,变种,3:,二分图的最大独立集,Girls and Boys,大学二年级的时候,一些同学开始研究男女同学之间的缘分。研究者试图找出没有缘分同学的最大集。程序的结果就是要输出这个集合中学生的数量。,hdoj_1068,精,29,变种3:二分图的最大独立集Girls and Boys,输入数据格式:,70: (3) 4 5 61: (2) 4 62: (0)3: (0)4: (2) 0 15: (1) 06: (2) 0 1,输出:,5,精,30,输入数据格式: 70: (3) 4 5 61: (2,0,0,1,5,4,3,2,6,5,4,3,2,1,6,“Girls and Boys”,示意图,精,31,00154326543216“Girls an,结论:,二分图的最大独立集数,=,节点数(,n,),最大匹配数(,m,),关键:,求二分图的最大匹配数,精,32,结论:二分图的最大独立集数=精32,Any Questions?,精,33,Any Questions?精33,附:二分匹配练习题:,(HDOJ),1068 (,二分图最大独立集,= n - m ),1150 (,二分图最小顶点覆盖,=m ),1151 (,二分图最小路径覆盖,= n - m ),精,34,附:二分匹配练习题:(HDOJ)1068 (二分图最大独,别忘了,,下周调课,(,西安,),精,35,别忘了,下周调课(西安)精35,课后一定要练习!,精,36,课后一定要练习!精36,ACM,天天见!,精,37,ACM,精37,
展开阅读全文