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

二分图最大匹配问题(贪心算法)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，N≤1000，代表用1，2，……，M和1，2，……，N表示）。他们被预先分成K(K≤60000)组进行谈判。每组两个人分别来自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值即为答案，直接输出即可。总结•以上就是简单明了的二分图最大匹配的贪心算法。•比起前面所提到的网络流算法和匈牙利算法，都有着无可比拟的优越性。•它不但比前面两个算法都要好理解，而且不及网络流算法的编程复杂度，也不用担心匈牙利算法的递归层数。注意•以上所述的贪心算法仅适用于二分图的最大匹配问题，最佳匹配问题是不适用的。•本人尚未见到有人能够对此算法给出严格的证明，但是网上确实也有不少人有用此算法过全点的经历。•总之，请各位慎重使用！（：以下附例题的主程序的代码主程序代码•procedureadd(i,j:longint);•begin•inc(top);•v[top]:=j;•next[top]:=u[i];•u[i]:=top;•inc(degree[i]);•end;•procedureins(i:longint);•varo:longint;•begin•visit[i]:=true;•inc(tot);•o:=u[i];•whileo0dobegin•dec(degree[v[o]]);•o:=next[o];•end;•end;•begin•readln(n,m,k);•fora:=1tokdobegin•readln(b,c);•c:=n+c;•add(b,c);•add(c,b);•end;主程序代码•n:=n+m;•whiletotndobegin•b:=maxlongint;//找结点u•fora:=1tondoif(notvisit[a])and(degree[a]b)thenbegin•b:=degree[a];•c:=a;•end;•a:=u[c];•b:=maxlongint;//找结点v•whilea0dobegin•if(notvisit[v[a]])and(degree[v[a]]b)thenbegin•b:=degree[v[a]];•d:=v[a];•end;•a:=next[a];•end;•inc(ans);//连边，答案加一•ins(c);//对u进行删除操作•ifbmaxlongintthenins(d);//如果存在v，对v进行删除操作•end;•writeln(ans);;•end.