二部图

二部图东华大学acm集训队二部图概念定义：设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集V1,V2之并，并且图中每条边依附的两个顶点都分属于这两个不同的子集。则称图G为二分图。二分图也可记为G=(V1,V2,E)。通俗的来说，由两个互不相交的点集X,Y，以及连接X，Y的一些无向边(X,Y内部无边相连)构成的一张图就叫二部图二部图的最大匹配对于二部图的最大匹配，我们以一个简单的例子来说明有3男4女找对象，只知道他们相互之间有好感，现在我们要给他们配对，要求每个人只能和一个异性配对，问你最多能配成多少对？我们把男生作为蓝色，女生作为红色二部图最大匹配不难看出，最多可以配成3对，然而，配对的方案却是不唯一的那么，现在我们把问题一般化，要你告诉n男m女互相有好感的关系，问你最多能配成多少对？这个问题如何解决？匈牙利算法思想：找增广路增广路定理：匹配是最大匹配当且仅当不存在增广路何为增广路？先介绍一些概念匹配：无公共点的边集合未盖点：不与任何匹配边邻接的点增广路从未盖点开始经过非匹配边、匹配边、非匹配边……序列，最终通过一条非匹配边到达另一个未盖点非匹配边个数比匹配边个数多一如果把匹配边和非匹配边互换…匹配仍合法，但基数加一匈牙利算法主要算法框架：1.初始化最大匹配数为02.每次从一个未盖点找一条增广路，若找到，最大匹配数加1，并把找到的增广路上的所有匹配边和未匹配边取反3.若所找的点集全部遍历完，算法结束匈牙利算法匹配数为0,所有y的link值为-1x1x2x3x4x5x6y1(-1)y2(-1)y3(-1)y4(-1)y5(-1)y6(-1)y7(-1)匈牙利算法访问x1x1x2x3x4x5x6y1(-1)y2(-1)y3(-1)y4(-1)y5(-1)y6(-1)y7(-1)匈牙利算法找到x1-y1,link[y1]=-1,为未盖点，停止，link[y1]=x1x1x2x3x4x5x6y1(x1)y2(-1)y3(-1)y4(-1)y5(-1)y6(-1)y7(-1)匈牙利算法访问x2,和x1类似x1x2x3x4x5x6y1(x1)y2(x2)y3(-1)y4(-1)y5(-1)y6(-1)y7(-1)匈牙利算法访问x3,找到增广路x3-y1-x1-y2-x2y5,修改y5x1x2x3x4x5x6y1(x1)y2(x2)y3(-1)y4(-1)y5(x2)y6(-1)y7(-1)匈牙利算法从y5沿路回退修改x1x2x3x4x5x6y1(x3)y2(x1)y3(-1)y4(-1)y5(x2)y6(-1)y7(-1)匈牙利算法访问x4,很简单x1x2x3x4x5x6y1(x3)y2(x1)y3(x4)y4(-1)y5(x2)y6(-1)y7(-1)匈牙利算法访问x5,也很简单x1x2x3x4x5x6y1(x3)y2(x1)y3(x4)y4(x5)y5(x2)y6(-1)y7(-1)匈牙利算法访问x6,找不到增广路算法结束，最大匹配数是5x1x2x3x4x5x6y1(x3)y2(x1)y3(x4)y4(x5)y5(x2)y6(-1)y7(-1)相关的代码boolmap[N][N];//邻接矩阵intnx,ny;//x,y点集的个数boolvis[N];//记录点有无被访问过intlink[N];//记录y集合到x集合映射关系intdfs(intu){for(inti=0;iny;i++){if(map[u][i]&&!vis[i]){vis[i]=1;if(link[i]==-1||dfs(link[i])){//y值被访问过就到它对应的x值继续向下找增广路link[i]=u;//在递归返回过程中不断修改return1;}}}return0;}相关的代码inthungry(){intans=0;memset(link,-1,sizeoflink);for(inti=0;inx;i++){memset(vis,0,sizeofvis);//每次必须清空，想一下为什么？ans+=dfs(i);}returnans;}总结从匈牙利算法中我们不难发现以下规律:1.增广路的长度必定是奇数，第一条边和最后一条边均为未匹配边2.每次增广路的匹配边和为匹配边取反均会使最大匹配数加一以上便是匈牙利算法的精髓所在，它的复杂度是O(n^3)当然也可以用bfs来实现，复杂度相当还有更快的一种叫Hopcroft算法，复杂度为感兴趣的同学可课后自行查资料()Onm例题uva259输入A401234;Q15;P456789;A401234;Q15;P556789;输出AAAA_QPPPP!