二分图最大匹配问题(贪心算法)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,二分图最大匹配问题,(,贪心算法,),BY,长郡中学 曹博凯,二分图的基本概念,二分图是一类特殊的图结构,二分图是这样一种图：,G,的顶点集合,V,分成两部分,X,与,Y,，,G,中每条边的两个端点一定是一个属于,X,而另一个属于,Y,。,匹配的基本概念,设,G=V,，,E,是一个无向图，,M,属于,E,是,G,的若干条边的集合，如果,M,中的任意两条边都没有公共的端点，就称,M,是一个匹配。,最大匹配的基本概念,从给定的图,G=V,，,E,的所有匹配中，把包含边数最多的匹配找出来。这种匹配即所谓的最大匹配问题。,二分图的最大匹配,e.g.,飞行员分成两部分，一部分是正驾驶员，一部分是副驾驶员。显然，如何搭配正副驾驶员才能使出航飞机最多的问题可以归结为一个二分图上的最大匹配问题。,常用算法,网络流算法（编程复杂，小题大做）,匈牙利算法（理解困难，实现简单）,以上这些我都不会怎么办？,不用急！,贪心算法,下面，我们引进一种能够完美解决二分图最大匹配问题的贪心算法。,理解容易,实现不难,会议安排,一个重要的会议由,A,公司的,M,位代表和,B,公司的,N,位代表参加（,M,，,N1000,，代表用,1,，,2,，,，,M,和,1,，,2,，,，,N,表示）。他们被预先分成,K(K60000),组进行谈判。每组两个人分别来自,A,公司和,B,公司。每个参加会议的代表都至少参加了一组谈判。会议为每一个代表都准备了一个房间。技术人员将会在一些房间之间连上直通电话，一个代表至少要和他的一个谈判对手直接联络。连接一个直通电话的价格是常数。技术人员要用尽量少的花费满足会议的要求。,题目分析,这道题目我们很容易将其抽象成为二分图最大匹配的基本模型。我们可以用匈牙利算法求出其最大匹配,M,，然后所求解即为,n+m,-M,。,可是，考场上并不是每个人都能想到这一巧妙的转换。,于是，我们可以怀抱着一种骗分的心态，构造出一种贪心策略，从而得到,满分,！,贪心算法,首先，我们将每条无向边拆分成两条反向的有向边，存储在邻接表中。与此同时，我们记录下每个顶点的出度。,然后，我们每次找出一个当前未被访问过的结点中，出度最小的结点,u,。同时，再在以该结点,u,为起始点的所有边所对的点中，找出一个同样满足未被访问，且出度最小的结点,v,。,贪心算法,接着，我们将,u,v,两点都进行,删除操作,。,（当,u,的出边所对的点都已被访问，那么就找不到满足条件的,v,，因此只对,u,进行操作）,所谓删除操作，在这里，删除,s,，其实就是将,s,的所有出边所对的点,t,的出度都减一。,（因为要删除点,s,，即,(,s,t,),也被删除，即,(,t,s,),也要被删除，所以,t,的出度要减一）,贪心算法,这样循环做下来，我们每做一次都相当于连了一条边（,u,v,），于是,inc(ans,),。,同时，我们对这条边的两个端点,u,v,都做了删除操作（如果可以的话）。每删一个点就,inc(tot,),，直到,tot=,n+m,，即两边的点均被删完。,此时我们得到的,ans,值即为答案，直接输出即可。,总结,以上就是简单明了的二分图最大匹配的贪心算法。,比起前面所提到的网络流算法和匈牙利算法，都有着无可比拟的优越性。,它不但比前面两个算法都要好理解，而且不及网络流算法的编程复杂度，也不用担心匈牙利算法的递归层数。,注意,以上所述的贪心算法仅适用于二分图的最大匹配问题，最佳匹配问题是不适用的。,本人尚未见到有人能够对此算法给出严格的证明，但是网上确实也有不少人有用此算法过全点的经历。,总之，请各位慎重使用！,（：以下附例题的主程序的代码,主程序代码,procedure,add(i,j:longint,);,begin,inc(top,);,vtop,:=j;,nexttop,:=,ui,;,ui,:=top;,inc(degreei,);,end;,procedure,ins(i:longint,);,var,o:longint,;,begin,visiti,:=true;,inc(tot,);,o:=,ui,;,while o0 do begin,dec(degreevo,);,o:=,nexto,;,end;,end;,begin,readln(n,m,k,);,for a:=1 to k do begin,readln(b,c,);,c:=,n+c,;,add(b,c,);,add(c,b,);,end;,主程序代码,n:=,n+m,;,while totn do begin,b:=,maxlongint,;/,找结点,u,for a:=1 to n do,if(not,visita)and(degreea,b)then,begin,b:=,degreea,;,c:=a;,end;,a:=,uc,;,b:=,maxlongint,;/,找结点,v,while a0 do begin,if(not,visitva)and(degreeva,b)then,begin,b:=,degreeva,;,d:=,va,;,end;,a:=,nexta,;,end;,inc(ans,);/,连边，答案加一,ins(c,);/,对,u,进行删除操作,if b,maxlongint,then,ins(d,);/,如果存在,v,，对,v,进行删除操作,end;,writeln(ans,);,end.,Thanks all.,