资源描述
,单击此处编辑母版样式,单击此处编辑幻灯片母版样式,第二层,第三层,第四层,第五层,*,精,*,单击此处编辑母版样式,单击此处编辑幻灯片母版样式,第二层,第三层,第四层,第五层,*,精,*,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,
展开阅读全文