一、题目链接

求二分图的最大匹配

二、题目链接

染色法判定是否为二分图

一、首先，看本篇博客前提是必须…

1

、如果不懂啥是

二分图

，先学习

染色法判定

是否为二分图的方法

二、形象讲解匈牙利算法

首先，我们所求

二分图匹配的概念为

：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集中的

任意两条边

都不依附于

同一个顶点

，则称 M 是

一个匹配

。

假设给我们一个二分图，左半部为四个点，右半部右四个点，如图：




我们可以把左半部分点当作四个男生，右半部分点当作四个女生


那么所求二分图最大匹配的过程，就是通过图当中的线段

寻求最多能匹配出

多少对情侣

的过程

则

原图的无向线段

就代表

两人之间有情愫

存在

所以情侣的匹配只能从有情愫(有连线的两人之间匹配)

int n1,n2,m；

首先我们用

n1,n2分别

代表

左半部男生

的数量，

右半部女生

的数量

我们不妨

从左半部为起点

来匹配右半部，也就是

从男1一直遍历到男4



来寻找

该男生是否能找到

所要匹配的女朋友




那么原图中的连线在男女二分图中就代表

两人有情感基础

，是

无向图



而

我们要

从男生的角度出发匹配的话

，只需要将

线段

变成

从男生指向女生


的

有向图

就够了

为了方便遍历各个男生喜欢的女生分别是谁

为此 我们用

数组实现的邻接表

来存这个图的数据

并定义int add(int a,int b)函数来

添加邻接表信息

int h[N],e[M],ne[M],idx;//邻接表

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

为了判断

某男生是否能找得到

女朋友

我们下面定义一个bool find(int x)函数来

判断


定义int match[N]数组//match[i]代表

女生i目前匹配的男朋友


定义int st[N] //我称它为预定数组,先看代码再解释

然后后续的图变化我没有画，我希望大家都自己画图模拟一下这个过程

bool find (int x)
{
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=true;
            if(match[j]==0 || find(match[j]))
                {
                    match[j]=x;
                    return true;
                }
        }
    }
    return false;
}

三、解释int st[N]的作用

重点:st[]的作用:

首先我们 find(x) 遍历属于

h[x]的单链表相当于遍历他所有喜欢的女生


而如果某个女生

j

没有被他预定过的话

就标记这个女生

j

被他预定,即

st[j]=true


这时如果女

j

还没有匹配过,即match[j]==0的时候,那这个预定就成真了,得到

match[j]=x

;

而如果女

j

之前就被男

k

匹配过了,那我们就find(k),也就是

find(match[j])(因为原本

match[j]==k

)

然后在find(k)的过程中,因为

st[j]=true

,这时候男

k

就不能再选则女

j

了,因为女

j

已经被预定了,

所以男

k

就只能在他喜欢的女生里面选择其他人来匹配。 当然，如果

find(k)返回false的话,


那就 if(match[j]==0 || find(match[j]))都不成立,

那男j就一边玩去把

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈嘿嘿嘿

完整代码

#include<iostream>
#include<cstring>
using namespace std;
int n1,n2,m;
const int N = 510,M=100010;
int h[N],e[M],ne[M],idx;
bool st[N];
int match[N];//match[i]用来记录i女生匹配的男生是几号
void add(int a,int b)
{
  e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool find (int x)
{
  for(int i=h[x];i!=-1;i=ne[i])
  {
      int j=e[i];
      if(!st[j])
      {
          st[j]=true;
          if(match[j]==0 || find(match[j]))
              {
                  match[j]=x;
                  return true;
              }
      }
  }
  return false;
}

int main()
{
  scanf("%d%d%d",&n1,&n2,&m);
  memset(h,-1,sizeof h);
  while(m--)
  {
      int u,v;
      scanf("%d%d",&u,&v);
      add(u,v);
  }
  int res=0;
  for(int i=1;i<=n1;i++)
      {
          memset(st,false,sizeof st);
          if(find(i)) res++;
      }
      cout<<res<<endl;
  
  return 0;
}

四、哪里有问题可互相评论交流

最后 yxcyyds 我爱acwing