【Note】二分图匹配 ＆ 题解：P3386

本文介绍匈牙利算法。
引入

一个无向图 \(G\)，\(G\) 中所有点可以被分为两个点集 \(A\) 和 \(B\)。\(G\) 中任意边均满足：该边所连两点分别属于 \(A\) 和 \(B\)。这样的图就叫二分图。
二分图最大匹配问题就是：选出一个边集 \(M\)，使任意一点所连的边中只有一条属于 \(M\)，问 \(M\) 中最多可以有多少边？
很难看对吧，换个大家喜闻乐见的方式

（这里是非诚勿扰）接下来有请男嘉宾登场！
目前有 \(n\) 个男孩和 \(m\) 个女孩，其中只能男女配对，男孩女孩间互有好感。
目前你已经知道那些男孩和女孩互有好感，你的任务是配对出尽量多的搭档。（对！仅仅是搭档！）
算法介绍

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

• 枚举和这个男孩互有好感的女孩。
  
• 如果该女孩还没被配对，那就组合成功。
  
• 如果该女孩已经被配对了，那就把她之前的搭档拆掉。让之前和她搭档的男孩（不妨设他编号为 \(j\)）重新找一个搭档（即男孩 \(j\) 进入找搭档流程）。
  
  
  
  • 如果男孩 \(j\) 找到了新搭档，就把男孩 \(i\) 和当前枚举的女孩配对。
    
  • 如果男孩 \(j\) 没找到新搭档，就让男孩 \(i\) 考虑下一个和他互有好感的女孩。
    
  
  
• 如果男孩 \(i\) 枚举完所有和他互有好感的女孩后都没戏，那他就只能和中国剩余定理（中国单身狗定理）殊途同归，成功落单了。
  

正确性及时间复杂度证明

匈牙利算法的正确性证明如下：
据 Berge 定理可知：一个匹配是最大匹配当且仅当图中不存在增广路径。算法为每个男孩尝试寻找增广路径：若找到，匹配数增加。若找不到，当前匹配数已最大化。综上，可证匈牙利算法的正确性。
设 \(n\) 为左侧节点数（男孩数，较小侧），\(m\) 为右侧节点数（女孩数），\(E\) 为总边数。
单次 DFS 的复杂度：DFS 遍历 \(u\) 的所有出边（即好感女孩），并通过维护一个布尔型数组确保每个女孩在单次 DFS 中仅被访问一次，每条边最多被访问一次（当检查女孩 \(v\) 时）。最坏情况下，单次的 DFS 时间复杂度为 \(O(E)\)（需遍历所有边）。
遍历所有 \(n\) 个男孩，对每个男孩跑 DFS，执行 \(n\) 次。每次 DFS 最坏为 \(O(E)\)。所以，总时间复杂度为 \(O(nE)\)。
代码实现

注释里已经讲的很清楚了，自己看代码吧。
洛谷 P3386 代码[code]#includeusing namespace std;int n,m,E,mat[1003],ans;//mat:和编号为i的girl配对的boy的编号bool vis[1003],F;//vis:编号为i的girl在这一轮有(true)没有(false)找过boyfriendvector e[502];//存边nly boy->girl//将题意转化为://有n个男孩,m个女孩和E个边//若1个男孩和1个女孩互有好感,可以配对,则称为有1个边//问最多能组成多少对lovers(a boy and a girl)//编号为i的男孩找girlfriend,找到返回true,没找到返回falsebool f(int u){        for(int v:e) 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