二分图

什么是二分图

二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集

(X,Y)，并且图中的每条边（i，j）

关联的两个顶点i和j分别属于这两个不同的顶点集X和 Y ， 则称图G为一个二分图。

什么是最大匹配

给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配.

选择这样的边数最大的子集称为图的最大匹配问题（maximalmatching problem)

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完美匹配.

同时二分图最大匹配问题又可以转化成“最小顶点覆盖”、“最小路径覆盖”、“最大独立集“等问题

匈牙利算法求二分图的最大匹配

算法的核心思想是由一个初始匹配不断找增广路，直到找不到增广路为止。这里的增广路和网络流中的增广路有些不同。这里的增广路是这样的一条路：设已有的匹配为M，它的第一条边不在M中，最后一条边也不在M中，中间为在M中的边与不在M中的边交错出现。显然，这条路起点在X中，终点在Y中，且不在M中的边比在M中的边多1。所以我们若对增广路中的边进行取反，即原来不是匹配边的边变为匹配边，原来是匹配边的边变为不是匹配边的边，则我们能获得一个更大的匹配。所以这么一直找下去，直到找不到增广路为止，我们最后得到的匹配M就是要求的最大匹配。

1 匈牙利算法中，初始匹配我们可以设为空，然后用DFS或者BFS找增广路。找一条增广路的复杂度为O（E），最多找V条增广路，故算法时间复杂度为O（VE）。

2 只要有找到增广路，就让ans++，为什么呢，因为一条增广路总是有未匹配的边比匹配边多1，那么如果取反后就相当与匹配边多1，那么就是ans++。

下面给出匈牙利算法的两种实现：

/*DFS实现二分图的最大匹配*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 1010
int Nx , Ny;/*Nx Ny分别表示的是左右两边的最大的集合的个数*/
int G[MAXN][MAXN];
int Mx[MAXN] , My[MAXN];/*Mx , My分别表示的是左右两边是否和另一边相连*/
bool mark[MAXN];/*标记右边的点是否被匹配过*/

/*查找增广路*/
bool FindPath(int u){
    /*枚举所有的右边集合的点*/
    for(int i = 1 ; i <= Ny ; i++){/*注意这个地方下标是从0开始还是1*/
       if(G[u][i] && !mark[i]){
         mark[i] = true;
         if(My[i] == -1 || FindPath(My[i])){
           /*互换*/
           My[i] = u;
           Mx[u] = i;
           return true;
         }   
       }
    }
    return false;
}

/*求最大的匹配*/
int MaxMatch(){
   int cnt = 0;
   memset(Mx , -1 , sizeof(Mx));/*左边集合初始话为空*/
   memset(My , -1 , sizeof(My));/*右边集合初始化为空*/
   /*每一次都找左边一个未匹配的点进行找增广路*/
   for(int i = 1 ; i <= Nx ; i++){/*注意这个地方下标是从0开始还是1*/
      if(Mx[i] == -1){
        memset(mark , 0 , sizeof(mark));
        if(FindPath(i))
          cnt++;
      }
   }
   return cnt;
}
int main(){
   /*建模*/
   printf("%d\n" , MaxMatch());
   return 0; 
}

2 BFS实现二分图的最大匹配
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 1010

int Nx , Ny;/*左边集合和右边集合*/
int G[MAXN][MAXN];/*存储关系的矩阵*/
int Mx[MAXN] , My[MAXN];/*左边和右边点和另外边相连的编号*/
int pre[MAXN] , Q[MAXN];
int mark[MAXN];

int MaxMatch(){
    int ans = 0;
    int front , rear;
    /*把左边和右边集合置为空*/
    memset(Mx , -1 , sizeof(Mx));
    memset(My , -1 , sizeof(My));
    memset(mark , -1 , sizeof(mark));
    
    for(int i = 1 ; i <= Nx ; i++){/*注意下标是从1开始还是0开始*/
       if(Mx[i] == -1){
          front = rear = 0;
          Q[rear++] = i;
          pre[i] = -1;

          bool flag = 0;

          while(front < rear && !flag){
              int u = Q[front];
              for(int v = 1 ; v <= Ny && !flag ; v++){/*注意下标是从1开始还是0开始*/
                 if(G[u][v] && mark[v] != i){
                   mark[v] = i;
                   Q[rear++] = My[v];
                   if(My[v] >= 0)
                     pre[My[v]] = u;
                   else{
                     flag = 1;
                     int d = u , e = v;
                     while(d != -1){
                         int t = Mx[d];
                         Mx[d] = e;
                         My[e] = d;
                         d = pre[d];
                         e = t;
                     }
                   }
                 }         
              }
              front++;
          }
          if(Mx[i] != -1)
            ans++;
       }
    }
    return ans;
}

int main(){
   /*建模*/
   printf("%d\n" , MaxMatch());
   return 0;
}