信息学竞赛算法分析与设计课件.ppt

1、1信息学竞赛信息学竞赛算法分析与设计算法分析与设计2本节课程内容本节课程内容(bipartite graph、matching)l 匈匈 牙牙 利利 算算 法法 lKuhn-Munkras算法算法3二分图的概念二分图的概念l二分图又称作二部图，是图论中的一种特殊模二分图又称作二部图，是图论中的一种特殊模型。型。l设设G=(V,R)是一个无向图。如顶点集是一个无向图。如顶点集V可分割可分割为两个互不相交的子集，并且图中每条边依附为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图的两个顶点都分属两个不同的子集。则称图G为二分图。为二分图。1122334454最大匹配最大

2、匹配l给定一个二分图给定一个二分图G，在，在G的一个子图的一个子图M中，中，M的边集的边集E中的任意两条边都不依附于同一个中的任意两条边都不依附于同一个顶点，则称顶点，则称M是一个匹配。是一个匹配。l选择这样的边数最大的子集称为图的最大匹配选择这样的边数最大的子集称为图的最大匹配问题问题(maximal matching problem)l如果一个匹配子图中，图中的每个顶点都和匹如果一个匹配子图中，图中的每个顶点都和匹配子图中某条边相关联，则称此匹配为完全匹配子图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。配，也称作完备匹配。5匈牙利算法匈牙利算法l求最大匹配的一种显而易见的算法是：

3、先找出全求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。一种更加高效的算法。l增广路的定义增广路的定义(也称增广轨或交错轨也称增广轨或交错轨)：若若P是图是图G中一条连通两个未匹配顶点的路径，中一条连通两个未匹配顶点的路径，并且属并且属M的边和不属的边和不属M的边的边(即已匹配和待匹配的即已匹配和待匹配的边边)在在P上交替出现，则称上交替出现，则称P为相对于为相对于M的一条增广的一条增广路径。路径。6匈牙利算法匈牙

4、利算法l由增广路的定义可以推出下述三个结论：由增广路的定义可以推出下述三个结论：1.P的路径长度必定为奇数，第一条边和最后一条边的路径长度必定为奇数，第一条边和最后一条边都不属于都不属于M。2.P经过取反操作可以得到一个更大的匹配经过取反操作可以得到一个更大的匹配M。3.M为为G的最大匹配当且仅当不存在相对于的最大匹配当且仅当不存在相对于M的增广的增广路径。路径。7匈牙利算法匈牙利算法l用增广路求最大匹配用增广路求最大匹配(称作匈牙利算法，称作匈牙利算法，匈牙利数学家匈牙利数学家Edmonds于于1965年提出年提出)l算法轮廓：算法轮廓：l(1)置置M为空为空l(2)找出一条增广路径找出一条

5、增广路径P，通过取反操作获得，通过取反操作获得更大的匹配更大的匹配M代替代替Ml(3)重复重复(2)操作直到找不出增广路径为止操作直到找不出增广路径为止8任给初始匹配找xV1为非饱和点S=x,T=取yN(s)-T存在一条从x到y的M可增广路P，M：=MP无法继续匹配，停止存在边y,u MS：=SuT：=T yM饱和V1N(s)=T?YNYNY已经饱和YN停止，M为最大匹配9设G是具有二部划分(V1,V2)的二分图.(1)任给初始匹配M;(2)若M饱和V1则结束.否则转(3);(3)在V1中找一非M饱和点x,置S=x,T=;(4)若N(S)=T,则停止,否则任选一点yN(S)-T;(5)若y为M

6、饱和点转(6),否则作求一条从x到y的M可增广路P,置M=MP,转(2)(6)由于y是M饱和点,故M中有一边y,u,置S=Su,T=Ty,转(4).匈牙利算法步骤匈牙利算法步骤10匈牙利算法匈牙利算法程序清单：#include#includebool g201201;int n,m,ans;bool b201;int link201;11匈牙利算法匈牙利算法bool init()int _x,_y;memset(g,0,sizeof(g);memset(link,0,sizeof(link);ans=0;if(scanf(“%d%d”,&n,&m)=EOF)return false;for(i

7、nt i=1;i=n;i+)scanf(“%d”,&_x);for(int j=0;j_x;j+)scanf(“%d”,&_y);g i _y=true;return true;12匈牙利算法匈牙利算法bool find(int a)for(int i=1;i=m;i+)if(ga i=1&!b i)b i=true;if(link i=0|find(link i)link i=a;return true;return false;13匈牙利算法匈牙利算法int main()while(init()for(int i=1;i=wi,j 成立成立(wi,j表示边的权表示边的权)，且，且对所有的边

8、对所有的边(i,j)in M,都有都有lxi+lyj=wi,j成立，成立，则则M是图是图G的一个最佳匹配。的一个最佳匹配。25KM算法算法l对于任意的对于任意的G和和M，可行顶标都是存在的：，可行顶标都是存在的：ll(x)=maxw(x,y)ll(y)=0l欲求完全二分图的最佳匹配，只要用匈牙利算法欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹配；问题是当标号之后的求其相等子图的完备匹配；问题是当标号之后的Gl无完备匹配时怎么办？无完备匹配时怎么办？1957年年Kuhn和和Munkras 给给出了一个解决该问题的有效算法，用出了一个解决该问题的有效算法，用逐次修改可行顶标逐次修

9、改可行顶标l(v)的办法使对应的相等子图之的办法使对应的相等子图之最大匹配逐次增广，最后出现完备匹配。最大匹配逐次增广，最后出现完备匹配。26KM算法算法l修改方法如下：修改方法如下：l先将一个未被匹配的顶点先将一个未被匹配的顶点u(u in x)做一次做一次增广路，记下哪些结点被访问那些结点没有增广路，记下哪些结点被访问那些结点没有被访问。求出被访问。求出d=minlxi+lyj-wi,j其中其中i结点被访问，结点被访问，j结点没有被访问。然后调整结点没有被访问。然后调整lx和和ly：对于访问过的：对于访问过的x顶点，将它的可行标顶点，将它的可行标减去减去d，对于所有访问过的，对于所有访问过

10、的y顶点，将它的可顶点，将它的可行标增加行标增加d。修改后的顶标仍是可行顶标，。修改后的顶标仍是可行顶标，原来的匹配原来的匹配M仍然存在，相等子图中至少出仍然存在，相等子图中至少出现了一条不属于现了一条不属于M的边，所以造成的边，所以造成M的逐渐的逐渐增广。增广。27KM算法算法l上述算法的证明也很容易上述算法的证明也很容易lKuhnMunkras算法流程：算法流程：l(1)初始化可行顶标的值初始化可行顶标的值l(2)用匈牙利算法寻找完备匹配用匈牙利算法寻找完备匹配l(3)若未找到完备匹配则修改可行顶标的值若未找到完备匹配则修改可行顶标的值l(4)重复重复(2)(3)直到找到相等子图的完备匹配

11、直到找到相等子图的完备匹配为止为止28作业：作业：l1325 Machine Schedule l2062 Card Game Cheater l2195 Going Home l2226 Muddy Fields 29附录：附录：l1 1 Place the Robots（ZOJ）l2 2 救护伤员（TOJ1148）l3 打猎l4 最小路径覆盖l5 一些例子l6 二部图相关的定义、定理30例题例题1 1 Place the Robots（ZOJ1654ZOJ1654）问题描述 有一个N*M(N,M=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一

12、列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。Wall Grass Empty31例题例题1 Place the Robots（ZOJ）模型一5467832112346578于是，问题转化为求图的最大独立集问题。在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：32例题例题1 Place the Robots（ZOJ）模型一5467832112346578在问题的原型中，草地，墙这些信息不是

13、我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：这是NP问题！33我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把这些块编上号。同样，把竖直方向的块也编上号。例题例题1 Place the Robots（ZOJ）模型二12345123434例题例题1 Place the Robots（ZOJ）模型二123451234把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二部

14、图：11223344535由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。例题例题1 Place the Robots（ZOJ）模型二12341235411223344536比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充分抓住了问题的内在联系，巧妙地建立了二部图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由此可见，对要素的选取，是图论建模中至关重要的一步。

15、例题例题1 Place the Robots（ZOJ）小结37例题例题2 2 救护伤员救护伤员（TOJ1148TOJ1148）l无情的海啸夺取了无数人的生命无情的海啸夺取了无数人的生命.很多的医疗很多的医疗队被派往灾区拯救伤员队被派往灾区拯救伤员.就在此时就在此时,医疗队突然医疗队突然发现自己带的药品已经不够用了发现自己带的药品已经不够用了,只剩下了只剩下了N种。种。(1 n=20)，随着病人病情的发展，随着病人病情的发展，每种药在每天能获得的效果是不一样的。同时，每种药在每天能获得的效果是不一样的。同时，每天病人只能服用一种药。也就是说，这些药每天病人只能服用一种药。也就是说，这些药还够支持

16、还够支持N天。现在，给出你每种药在每天使天。现在，给出你每种药在每天使用的效果，请你判断当每种药都用完后所有药用的效果，请你判断当每种药都用完后所有药达到的效果之和最大可以是多少。达到的效果之和最大可以是多少。38例题例题3 3 打猎打猎l猎人要在猎人要在n*n的格子里打鸟，他可以在某一行的格子里打鸟，他可以在某一行中打一枪，这样此行中的所有鸟都被打掉，也中打一枪，这样此行中的所有鸟都被打掉，也可以在某一列中打，这样此列中的所有鸟都打可以在某一列中打，这样此列中的所有鸟都打掉。问至少打几枪，才能打光所有的鸟？掉。问至少打几枪，才能打光所有的鸟？l建图：二分图的建图：二分图的X部为每一行，部为每

17、一行，Y部为每一列，部为每一列，如果如果(i,j)有一只鸟，那么连接有一只鸟，那么连接X部的部的i与与Y部的部的j。l该二分图的最大匹配数则是最少要打的枪数。该二分图的最大匹配数则是最少要打的枪数。39例题例题4 4 最小路径覆盖最小路径覆盖l一个不含圈的有向图一个不含圈的有向图G中，中，G的一个路径覆盖的一个路径覆盖是一个其结点不相交的路径集合是一个其结点不相交的路径集合P，图中的每，图中的每一个结点仅包含于一个结点仅包含于P中的某一条路径。路径可中的某一条路径。路径可以从任意结点开始和结束，且长度也为任意值，以从任意结点开始和结束，且长度也为任意值，包括包括0。请你求任意一个不含圈的有向图

18、。请你求任意一个不含圈的有向图G的的最小路径覆盖数。最小路径覆盖数。l理清一个关系：最小路径覆盖数理清一个关系：最小路径覆盖数G的结点数的结点数最小路径覆盖中的边数最小路径覆盖中的边数40例题例题4 最小路径覆盖最小路径覆盖l试想我们应该使得最小路径覆盖中的边数尽量多，试想我们应该使得最小路径覆盖中的边数尽量多，但是又不能让两条边在同一个顶点相交。但是又不能让两条边在同一个顶点相交。l拆点：将每一个顶点拆点：将每一个顶点i拆成两个顶点拆成两个顶点Xi和和Yi。然后。然后根据原图中边的信息，从根据原图中边的信息，从X部往部往Y部引边。所有边部引边。所有边的方向都是由的方向都是由X部到部到Y部。部

19、。41例题例题4 最小路径覆盖最小路径覆盖l因此，所转化出的二分图的最大匹配数则是原因此，所转化出的二分图的最大匹配数则是原图图G中最小路径覆盖上的边数。因此由最小路中最小路径覆盖上的边数。因此由最小路径覆盖数原图径覆盖数原图G的顶点数二分图的最大匹的顶点数二分图的最大匹配数便可以得解。配数便可以得解。42例1 m项工作准备分给n个人去做，如图，其中边（xi,yj)表示xi,可以从事yj，如果每个人最多从事其中一项，且每项工作只能由一人担任。问怎样才能使尽可能多的人安派上任务。y1y2y3y4y5x1x2x3x4x5二分图，如xj从事了yi就不能从事yk,同时yi也不允许其它人担任。相当于用一

20、种颜色，例如红色，对G的边着色，保证每个结点最多与一条红色边相联，这种红色边的集合记为M它是图G的一个匹配。计算G中边数最多的匹配。43例2 二次大站期间，许多盟军飞行员到英国参加对法西斯的空袭，当时每架飞机需领航员和飞行员各一名。其中有些只能领航，有些只能驾驶，也有人二者均会。加之二人语言要求相通，如果以结点表示人，边表示二人语言相通并且一人可领航，另一人可驾驶一可得一图，这是一简单图那么最多的编队方案就是求成过急G的一个最大匹配。44例.有n张纸牌,每张纸牌的正反两面都写上1,2,n的某一个数,证明:如果每个数字恰好出现两次,则这些纸牌一定可以这样摊开,使朝上的面中1,2,n都出现.45例

21、 某工厂生产由6种不同颜色的纱织成的布，由这个工厂生产的双色布中每一种颜色至少和其它三种颜色搭配。证明可以挑选出三种不同的双色布，他们含有所有的6种颜色。46二部图：二部图：一些例子一些例子l作者作者-文章文章(author-literature)l演员演员-电影电影(actor-film)l基因基因-疾病疾病(gene-disease)l药物药物-靶标靶标(drug-protein target)l基础医学和临床中的数据？基础医学和临床中的数据？l。47相关定义、定理相关定义、定理l定理定理1：简单图简单图G为二部图为二部图G中所有基本回路的长中所有基本回路的长度为偶数。度为偶数。l定义定义

22、1：设无向图设无向图G，M E，若，若M中任意两中任意两条边都不相邻，则称条边都不相邻，则称M为为G的一个匹配的一个匹配，并把，并把M中的中的边所关联的两个结点称为边所关联的两个结点称为在在M下是匹配的下是匹配的。若在。若在M中中再加入任何一条边就不是匹配了，称再加入任何一条边就不是匹配了，称M为极大匹配为极大匹配。边数最多的极大匹配称为边数最多的极大匹配称为G的最大匹配的最大匹配。最大匹配中。最大匹配中的边的个数称为的边的个数称为G的匹配数的匹配数。M是是G中的一个匹配，若结点中的一个匹配，若结点v与与M中的边关联，称中的边关联，称v为为M饱和点饱和点，否则称，否则称v为为M非饱和点。若非饱

23、和点。若G中每个结中每个结点都是点都是M饱和点，称饱和点，称M是完全匹配是完全匹配。48l定义定义2：设：设G为二部图，为二部图，M是是G中一个最大匹配，若中一个最大匹配，若|M|min|V1|，|V2|，称称M为为G中的一个完备匹配。若此时中的一个完备匹配。若此时|V1|V2|，称称M为为V1到到V2的一个完备匹配。若的一个完备匹配。若|V1|V2|，称称M为为G的完全匹配。的完全匹配。l定理定理3(Hall定理定理)：设：设G，|V1|V2|，G中存在从中存在从V1到到V2的完备匹配的完备匹配V1中任意中任意k个结点个结点(k1，2，|V1|)至少至少邻接邻接V2中的中的k个结点。个结点。

24、49l定理定理4(t条件条件)：设：设G，若，若V1中中每个结点至少关联每个结点至少关联t(t0)条边，而条边，而V2中每个结中每个结点至多关联点至多关联t条边，则条边，则G中存在中存在V1到到V2的完备的完备匹配。匹配。l推论：推论：G，对任意，对任意vV1或或V2有有d(v)k0，则，则G有一个完全匹配。有一个完全匹配。50 例：某大学计算机系有例：某大学计算机系有3个课外学习小组：网络组、网页个课外学习小组：网络组、网页制作组和数据库组。今有张、王、李、赵、陈制作组和数据库组。今有张、王、李、赵、陈5名同学。若名同学。若已知：已知：(1)张、王为网络组成员，张、李、赵为网页制作组成张、王

25、为网络组成员，张、李、赵为网页制作组成员，李、赵、陈为数据库组成员；员，李、赵、陈为数据库组成员；(2)张为网络组成员，王、李、赵为网页制作组成员，张为网络组成员，王、李、赵为网页制作组成员，王、李、赵、陈为数据库组成员；王、李、赵、陈为数据库组成员；(3)张为网络组和网页制作组成员，王、李、赵、陈为张为网络组和网页制作组成员，王、李、赵、陈为数据库组成员。数据库组成员。问以上问以上3种情况下能否各选出种情况下能否各选出3名不兼职的组长？名不兼职的组长？51例例 某中学有某中学有3个课外小组个课外小组:物理组、化学组、物理组、化学组、生物组生物组.今有张、王、李、赵、陈今有张、王、李、赵、陈5

26、名同学名同学.若已知若已知:l(1)张、王为物理组成员张、王为物理组成员,张、李、赵为化张、李、赵为化学组成员学组成员,李、赵、陈为生物组成员李、赵、陈为生物组成员;l(2)张为物理组成员张为物理组成员,王、李、赵为化学组王、李、赵为化学组成员成员,王、李、赵、陈为生物组成员王、李、赵、陈为生物组成员;l(3)张为物理组和化学组成员张为物理组和化学组成员,王、李、赵、王、李、赵、陈为生物组成员陈为生物组成员.问在以上问在以上3种情况下能否各选出种情况下能否各选出3名不兼职名不兼职的组长？的组长？52解：设解：设v1，v2，v3，v4，v5分别表示张、王、李、赵、分别表示张、王、李、赵、陈，陈，

27、u1，u2，u3分别表示网络组、网页制作组、数据分别表示网络组、网页制作组、数据库组，则根据上述三种情况得到的二部图如图库组，则根据上述三种情况得到的二部图如图10-26所示。所示。53G1满足满足t=2的的t条件条件,所以所以,存在从存在从V1=u1,u2,u3到到V2=v1,v2,v3,v4,v5的完备匹的完备匹配配,图中粗边所示的匹配就是其中的一个图中粗边所示的匹配就是其中的一个,即即选张为物理组组长、李为化学组组长、赵为选张为物理组组长、李为化学组组长、赵为生物组组长生物组组长.G2不满足不满足t条件条件,但满足相异性条件但满足相异性条件,因因而也存在完备匹配而也存在完备匹配,图中粗边

28、所示匹配就是图中粗边所示匹配就是其中的一个完备匹配其中的一个完备匹配.G3不满足不满足t条件条件,也不满足相异性条件也不满足相异性条件,因而不存在完备匹配因而不存在完备匹配,故选不出故选不出3名不兼职的名不兼职的组长来组长来.54 因为图因为图(a)满足满足t2的的t条件，所以图条件，所以图(a)中存在完中存在完备匹配，如图备匹配，如图(a)中粗线所示。图中粗线所示。图(b)满足相异性条件，满足相异性条件，图图(b)中存在完备匹配，如图中存在完备匹配，如图(b)中粗线所示。而图中粗线所示。而图(c)不满足不满足t条件，也不满足相异性条件，所以图条件，也不满足相异性条件，所以图(b)不存不存在完备匹配。故上述问题中在完备匹配。故上述问题中(1)和和(2)有解，而有解，而(3)无解。无解。