最大二分匹配 匈牙利算法

二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

---

二分图的最大匹配：

       给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。所有M中变数最多的一个匹配称为最大二分匹配

         求二分图最大匹配可以用最大流或者匈牙利算法。

---

用到的关键结构：  link[ m ] : 保存最终每一个m中的 j 匹配的对象，如果匹配的是i  j 则 link[ j ] = i;

                              map[ n ][ m ]:记录i j 之间是否可以匹配

                              visited[ m ]： 标记在每一次寻找匹配时j是否已经被其他对象匹配

 

---

主要讲匈牙利算法（主要步骤）：

     1、根据题意建立一个map[ n ][ m ]  ,map[ i ] [ j ] 代表i与j是否存在匹配

     

     2、对n中的每个i 去寻找是否存在匹配

---

主要代码实现：

int  main( ) {

     memset(link, (int)-1, sizeof(link));

     for(int i=0; i

          memset(visited, 0, sizeof(visited));

          if( findmatch(i) ) res++;

     }

     return 0;

}

bool findmatch(int x){

     for(int j=0; j

    在此次递归寻找匹配的过程中x与j可以匹配  visited 用来标记在此次递归寻找匹配的过程中j是否已经于另外的匹配了

          if( map[ x] [ j ] == 1 && visited[ j ] == 0){

               visited[ j ] =1;

               如果j 未与其他的对象进行匹配 或者是与j匹配的对象可以寻找另外的匹配 让出当前占用对象   那么就将x与j进行匹配

               if(link[ j ] == -1  ||  findmatch( link[ j ] )){

                         link[ j ] = x;

                         return true;

               }

               visited[ j ] = 0;

          }

     }

     return false;

}

     

---

匈牙利算法可以解决的图的问题：（二分图）
1.图的最小点覆盖数 = 图的最大匹配数；
2.图的最大点独立集 = 图顶点数 - 图的最大匹配数；
3.图的最小路径覆盖数 = 原图的顶点数 - 原图拆点后形成的二部图的最大匹配数；

 1的证明可以用反证法，若最大匹配数M（最小点数）不能覆盖所有边，则存在额外的边e，把e加入可以得到更大的M。矛盾。

最小路径覆盖数：   

       一个A个结点的有向无环图中，路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）。

       路径覆盖与二分图匹配的关系（必须是没有圈的有向图）：最小路径覆盖=|A|－分拆后最大匹配数

将A中i结点分拆一个B中i‘，则有限边中i->j 对应i->j'  原图的结点数-A与B的最大匹配数为最小路径覆盖。

证明根据自己的理解：首先将每个点看成一个路径即p->p 则覆盖所有点需要n个路径，在AB匹配中若对于i->j'则原图有i->j;这样选取此边可是路径数-1,因为在AB匹配中一个点对于一条边，所以在原图中一个点也对应一个边，即满足路径覆盖。。所以 原图的结点数-A与B的最大匹配数为最小路径覆盖。


附上hdu acm2063题解：

#include<stdio.h>
#include<algorithm>
using namespace std;
#define max 1000
int a,b,n,res,girl,boy;
int vist[max],map[max][max],link[max];
bool dfs(int x)
{
    int i;
   for(i=1;i<=boy;i++)
   {
       if(map[x][i]==1 && vist[i]==0)
       {
           vist[i]=1;
           if(link[i]==-1 || dfs(link[i]))
           {
               link[i]=x;
               return true;
           }
           vist[i]=0;
       }
   }
   return false;
}
int main()
{
    int i;
// freopen("E:\\test.txt","r",stdin);
   while(scanf("%d",&n) && n)
   {
       res=0;
       scanf("%d%d",&girl,&boy);
       memset(map,0,sizeof(map));
       for(i=0;i<n;i++)
       {
           scanf("%d%d",&a,&b);
           map[a][b]=1;
       }
       memset(link,(int)-1,sizeof(link));
       for(i=1;i<=girl;i++)
       {
           memset(vist,0,sizeof(vist));
           if(dfs(i))
           {
               res++;
           }
       }
       printf("%d\n",res);
   }
   return 0;
}