P3386 【模板】二分图最大匹配
基本概念
二分图定义
图G=(V,E)是二分图当且仅当存在顶点划分V = V_1 \cup V_2，满足：V_1 \cap V_2 = \emptyset,\quad \forall e=(u,v)\in E,\ u\in V_1 \land v\in V_2
匹配定义
边集M \subseteq E是匹配当且仅当：
\forall e_1,e_2 \in M,\ e_1 \neq e_2 \Rightarrow e_1 \cap e_2 = \emptyset
最大匹配是基数|M|最大的匹配。
匈牙利算法(hungary)
并不饿(hungry)。
核心思想
通过寻找增广路径（Augmenting Path）来迭代改进匹配：
初始匹配M = \emptyset
对每个未匹配的u \in V_1，尝试找到从u出发的增广路径
增广路径定义为：若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径（举例来说，有A、B集合，增广路由A中一个点通向B中一个点，再由B中这个点通向A中一个点……交替进行）。
简单地说，顾名思义，只要找到增广路，就可以得到更大匹配。
找到后执行对称差操作：M \leftarrow M \oplus P
时间复杂度
\mathcal{O}(N \cdot E) \quad \text{（最坏情况）}
其中n=|V_1|，e=|E|
算法流程
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
vector<int> G[maxn];
int match[maxn],ans=0;
bool matched[maxn];
bool find(int u){
for(int v:G[u]){
if(!matched[v]){
matched[v]=1;
if(!match[v]||find(match[v])){
match[v]=u;
return true;
}
}
}
return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,e;
cin>>n>>m>>e;
for(int i=0;i<e;i++){
int u,v;
cin>>u>>v;
G[u].push_back(v);
}
for(int i=1;i<=n;i++){
memset(matched,0,sizeof(matched));
if(find(i))ans++;
}
cout<<ans;
return 0;
}