首页 > 代码库 > 二分匹配
二分匹配
PS：二分图匹配这一章的内容，我认为最重要的是要弄清楚概念。
一些定义：
二分图：二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如
果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联
的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个
二分图。记为G=(A,B;E)。
二分图匹配：给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
需要强调的是：集合A或者B中，本集合中的元素之间是没有关系的。
最大匹配可用最大流来解，最佳匹配可用最大流最小费用流来解。
二分匹配的意义何在，最大匹配、最佳匹配算法的时间复杂度低。
一、最大匹配
最大匹配是找到匹配数最多的匹配。
DFS版匈牙利算法： 代码最简洁。时间复杂度为O(n*m), 空间复杂度为O(n*n)。
不卡时间大家都喜欢用这个。
BFS版匈牙利算法： 代码稍多。时间复杂度为O(n*m), 空间复杂度为O(n*n)
Hopcroft-Karp算法：对匈牙利算法进行了优化，时间复杂度O(m√n)。代码很长，空间复杂度为O(m*m)。
需要说明的是：准备模版的时候还是多准备一些比较好，有些题目是卡时间，有些却是卡空间。所以有些题目用好的算法就是AC不了。
DFS匈牙利算法模版：
1 //适合边比较多的图 2 const int N=300; 3 bool bmap[N][N],bmask[N]; 4 int cx[N],cy[N]; 5 int nx,ny,ans; 6 int findpath(int u) 7 { 8 int i,j; 9 for(i=1;i<=ny;i++)10 {11 if(bmap[u][i]&&!bmask[i])12 {13 bmask[i]=1;14 if(cy[i]==-1||findpath(cy[i]))15 {16 cy[i]=u; cx[u]=i;17 return 1;18 }19 }20 }21 return 0;22 }23 void maxmatch()24 {25 int i ,j;26 ans=0;27 for(i=1;i<=nx;i++) cx[i]=-1;28 for(i=1;i<=ny;i++) cy[i]=-1;29 for(i=1;i<=nx;i++)30 {31 if(cx[i]==-1)32 {33 for(j=1;j<=ny;j++)34 bmask[j]=0;35 ans+=findpath(i);36 }37 }38 }39 void init()40 {41 memset(bmap,0,sizeof(bmap));42 }43 44 (2)匈牙利算法BFS 时间复杂度O(n*m)45 46 const int N=1010;47 int bmap[N][N],cx[N],cy[N],bmask[N],que[N],pre[N];48 int nx,ny,ans;49 void maxmatch()50 {51 ans=0;52 int qs,qe;53 memset(cx,-1,sizeof(cx));54 memset(cy,-1,sizeof(cy));55 memset(bmask,-1,sizeof(bmask));56 for(int i=1;i<=nx;i++)57 {58 if(cx[i] == -1)59 {60 qs=qe=0;61 que[qe++]=i;62 pre[i]=-1;63 bool flag=0;64 while(qs<qe&&!flag)65 {66 int u=que[qs];67 for(int v=1;v<=ny&&!flag;v++)68 {69 if(bmap[u][v]&&bmask[v]!=i)70 {71 bmask[v]=i;que[qe++]=cy[v];72 if(cy[v]>=0) pre[cy[v]]=u;73 else74 {75 flag=1;76 int d=u,e=v;77 while(d!=-1)78 {79 int t=cx[d];80 cx[d]=e; cy[e]=d;81 d=pre[d]; e=t;82 }83 }84 }85 }86 qs++;87 }88 if(cx[i]!=-1) ans++;89 }90 }91 }92 void init()93 {94 memset(bmap,0,sizeof(bmap));95 }
Hopcroft-Karp算法模版：有时候顶点较多，所以直接用邻接表，没用邻接矩阵。
1 const int N=10150,INF=0x3f3f3f3f; 2 int cx[N],cy[N],dx[N],dy[N]; 3 bool bmask[N]; 4 int nx,ny,dis,ans; 5 vector<int> bmap[N]; 6 bool searchpath() 7 { 8 queue<int> q; 9 dis=INF;10 memset(dx,-1,sizeof(dx));11 memset(dy,-1,sizeof(dy));12 for(int i=1;i<=nx;i++)13 {14 if(cx[i]==-1){ q.push(i); dx[i]=0; }15 while(!q.empty())16 {17 int u=q.front(); q.pop();18 if(dx[u]>dis) break;19 for(int i=0;i<bmap[u].size();i++)20 {21 int v=bmap[u][i];22 if(dy[v]==-1)23 {24 dy[v]= dx[u] + 1;25 if(cy[v]==-1) dis=dy[v];26 else27 {28 dx[cy[v]]= dy[v]+1;29 q.push(cy[v]);30 }31 }32 }33 }34 }35 return dis!=INF;36 }37 int findpath(int u)38 {39 for(int i=0;i<bmap[u].size();i++)40 {41 int v=bmap[u][i];42 if(!bmask[v]&&dy[v]==dx[u]+1)43 {44 bmask[v]=1;45 if(cy[v]!=-1&&dy[v]==dis) continue;46 if(cy[v]==-1||findpath(cy[v]))47 {48 cy[v]=u; cx[u]=v;49 return 1;50 }51 }52 }53 return 0;54 }55 void maxmatch()56 {57 ans=0;58 memset(cx,-1,sizeof(cx));59 memset(cy,-1,sizeof(cy));60 while(searchpath())61 {62 memset(bmask,0,sizeof(bmask));63 for(int i=1;i<=nx;i++)64 if(cx[i]==-1) ans+=findpath(i);65 }66 }67 void init()68 {69 for(int i=0;i<N;i++) bmap[i].clear();70 }
题目类型：
1、判断是否构成二分图 http://www.cnblogs.com/Potato-lover/p/3985869.html
2、二分 + 最大匹配 http://www.cnblogs.com/Potato-lover/p/3989675.html
3、奇偶建图 http://www.cnblogs.com/Potato-lover/p/3991533.html
二、最佳匹配
与最大匹配不同的是，最佳匹配是在每一个匹配之间加一个权值。求的就是权值之和最大的匹配。
Kuhn Munkras 算法：时间复杂度为O(m*m*n)。
模版：
1 const int N=110, INF=0x3f3f3f3f; 2 int Map[N][N],mat1[N],mat2[N]; 3 int KM(int m,int n) 4 { 5 int s[N],t[N],a[N],b[N]; 6 int i,j,k,p,q,ans=0; 7 for(i=0;i<m;i++) 8 { 9 a[i]=-INF;10 for(j=0;j<n;j++)11 a[i]=Map[i][j]>a[i]?Map[i][j]:a[i];12 if(a[i]==-INF) return -1;//cannot match13 }14 memset(b,0,sizeof(b));15 memset(mat1,-1,sizeof(mat1));16 memset(mat2,-1,sizeof(mat2));17 for(i=0;i<m;i++)18 {19 memset(t,-1,sizeof(t));20 p=q=0;21 for(s[0]=i;p<=q&&mat1[i]<0;p++)22 {23 for(k=s[p],j=0;j<n&&mat1[i]<0;j++)24 {25 if(a[k]+b[j]==Map[k][j]&&t[j]<0)26 {27 s[++q]=mat2[j]; t[j]=k;28 if(s[q]<0)29 for(p=j;p>=0;j=p)30 {31 mat2[j]=k=t[j];p=mat1[k]; mat1[k]=j;32 }33 }34 }35 }36 if(mat1[i]<0)37 {38 i--,p=INF;39 for(k=0;k<=q;k++)40 {41 for(j=0;j<n;j++)42 if(t[j]<0&&a[s[k]]+b[j]-Map[s[k]][j]<p)43 p=a[s[k]]+b[j]-Map[s[k]][j];44 }45 for(j=0;j<n;j++) b[j]+=t[j]<0?0:p;46 for(k=0;k<=q;k++) a[s[k]]-=p;47 }48 }49 for(i=0;i<m;i++) ans+=Map[i][mat1[i]];50 return ans;51 }52 void init()53 {54 for(int i=0;i<N;i++)55 for(int j=0;j<N;j++)56 Map[i][j]=-INF;57 }
题目：
http://www.cnblogs.com/Potato-lover/category/615224.html
三、多重匹配
最大匹配值允许A集合与B集合是一一对应。多重匹配可以使得B的元素与多个A的元素匹配。
算法模版：
1 const int N=1010; 2 int cy[N][N],vcy[N]; 3 bool bmask[N],bmap[N][N]; 4 int nx,ny,limit,L,R; 5 bool findpath(int u) 6 { 7 int i,j; 8 for(i=1;i<=ny;i++) 9 {10 if(bmap[u][i]&&!bmask[i])11 {12 bmask[i]=1;13 if(vcy[i]<limit)14 {15 cy[i][++vcy[i]] =u;16 return 1;17 }18 for(j=1;j<=vcy[i];j++)19 {20 if(findpath(cy[i][j]))21 {22 cy[i][j]=u;23 return 1;24 }25 }26 }27 }28 return 0;29 }30 bool mulmatch()31 {32 memset(vcy,0,sizeof(vcy));33 for(int i=1;i<=nx;i++)34 {35 memset(bmask,0,sizeof(bmask));36 if(!findpath(i)) return 0;37 }38 return 1;39 }40 void init()41 {42 memset(bmap,0,sizeof(bmap));43 }44 int main()45 {46 L=0,R=nx;47 while(L<=R)48 {49 limit=(L+R)/2;50 if(mulmatch()) R=limit-1;51 else L=limit+1;52 }53 printf("%d\n",L);54 }
题目：
2289 Jamie‘s Contact Groups
四、二分图模型的应用
1、二分图最小点覆盖 http://www.cnblogs.com/Potato-lover/p/3980411.html
2、有向无环图的最小路径覆盖 http://www.cnblogs.com/Potato-lover/p/3989625.html
3、二分图的最大独立集 http://www.cnblogs.com/Potato-lover/p/3980491.html
二分匹配