【Note】二分图最大匹配 - boy and girl（P3386 题解）

· · 题解

本文介绍匈牙利算法，博客食用更佳。

引入

一个无向图 G，G 中所有点可以被分为两个点集 A 和 B。G 中任意边均满足：该边所连两点分别属于 A 和 B。这样的图就叫二分图。

二分图最大匹配问题就是：选出一个边集 M，使任意一点所连的边中只有一条属于 M，问 M 中最多可以有多少边？

很难看对吧，换个大家喜闻乐见的方式

（这里是非诚勿扰）接下来有请男嘉宾登场！

目前有 n 个男孩和 m 个女孩，其中只能男女配对，男孩女孩间互有好感。

目前你已经知道那些男孩和女孩互有好感，你的任务是配对出尽量多的搭档。（对！仅仅是搭档！）

算法介绍

具体的，若男孩 u 和女孩 v 互有好感，就建一条连接 u 和 v 的边。于是，我们就能拿到一张关系表二分图。接下来枚举每个男孩（强制 n \le m，可以优化常数），让男孩（设他编号为 i）进入找搭档流程（即在二分图上跑如下流程的 DFS）：

正确性及时间复杂度证明

Berge 定理

我们在二分图上找一条路径，若路径由选中的边（即该边所连的男孩和女孩决定配对）和没选中的边交替组成，且第一条边和最后一条边均未被选，我们称该路径为增广路径。容易发现，我们把任意增广路上的边的被选状态反转（即之前没选的选上，之前选了的又不选了），方案依然合法，且被选中的边数还比之前多一条（即多了一对搭档）。

由此可知，存在增广路径就代表还有更优方案，最终我们就得到了 Berge 定理：一个匹配是最大匹配当且仅当图中不存在增广路径。

而匈牙利算法为每个男孩尝试寻找增广路径：若找到，匹配数增加。若找不到，当前匹配数已最大化。综上，可证匈牙利算法的正确性。

设 n 为左侧节点数（男孩数，较小侧），m 为右侧节点数（女孩数），E 为总边数。

单次 DFS 的复杂度：DFS 遍历 u 的所有出边（即好感女孩），并通过维护一个布尔型数组确保每个女孩在单次 DFS 中仅被访问一次，每条边最多被访问一次（当检查女孩 v 时）。最坏情况下，单次的 DFS 时间复杂度为 O(E)（需遍历所有边）。

遍历所有 n 个男孩，对每个男孩跑 DFS，执行 n 次。每次 DFS 最坏为 O(E)。所以，总时间复杂度为 O(nE)。

代码实现

注释里已经讲的很清楚了，自己看代码吧。

#include<bits/stdc++.h>
using namespace std;
int n,m,E,mat[1003],ans;
//mat[i]:和编号为i的girl配对的boy的编号
bool vis[1003],F;
//vis:编号为i的girl在这一轮有(true)没有(false)找过boyfriend
vector<int> e[502];//存边:only boy->girl
//将题意转化为:
//有n个男孩,m个女孩和E个边
//若1个男孩和1个女孩互有好感,可以配对,则称为有1个边
//问最多能组成多少对lovers(a boy and a girl)

//编号为i的男孩找girlfriend,找到返回true,没找到返回false
bool f(int u){
    for(int v:e[u]) if(!vis[v]){
//      枚举和编号为u的男孩互有好感且本轮还没找过boyfriend的女孩
        vis[v]=true;//编号为i的girl找过boyfriend了
        if(mat[v]==0||f(mat[v])){//可否配对
            mat[v]=u;
            return true;
        }
    }
    return false;
}

int main(){
    scanf("%d%d%d",&n,&m,&E);
    if(n>m) swap(n,m),F=true;//强制定义人少的那一方是男孩
    for(int i=1,u,v;i<=E;i++){
        scanf("%d%d",&u,&v);
        if(F) swap(v,u);
//      如故男孩是因为强制转换变为人少的那一方,那这里也要转换
        e[u].push_back(v+n);
//      防止boy和girl编号重复,给girl的编号加上n
    }
    for(int i=1;i<=n;i++){//枚举每一个男孩
        memset(vis,0,sizeof(vis));
        if(f(i)) ans++;//若编号为i的男孩配对成功了,那么ans加1
    }
    printf("%d",ans);
    return 0;
}