二分图最大匹配
二分图最大匹配：给定一个二分图 G，即分左右两部分，各部分之间的点没有边连接，要求选出一些边，使得这些边没有公共顶点，且边的数量最大。
增广路算法 Augmenting Path Algorithm
因为增广路长度为奇数，路径起始点非左即右，所以我们先考虑从左边的未匹配点找增广路。
注意到因为交错路的关系，增广路上的第奇数条边都是非匹配边，第偶数条边都是匹配边，于是左到右都是非匹配边，右到左都是匹配边。
于是我们给二分图 定向，问题转换成，有向图中从给定起点找一条简单路径走到某个未匹配点，此问题等价给定起始点 s 能否走到终点 t。
那么只要从起始点开始 DFS 遍历直到找到某个未匹配点，O(m)。
未找到增广路时，我们拓展的路也称为 交错树。
因为要枚举 n 个点，总复杂度为 O(nm)。
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
cs int N=5e4+5;
int h[1005];
int had_cp[1005],cp[1005];
namespace edge{
struct qwq{
int v,nxt;
}e[N];
il void add(int u,int v,int id){
e[id]={v,h[u]},h[u]=id;
}
} using namespace edge;
namespace Bipartite_graph{
bool have_cp(int u,int tim){
for(ri int i=h[u];i;i=e[i].nxt){
if(had_cp[e[i].v]!=tim){
had_cp[e[i].v]=tim;
if(!cp[e[i].v]||have_cp(cp[e[i].v],tim)){
cp[e[i].v]=u;
return 1;
}
}
}
return 0;
}
} using namespace Bipartite_graph;
int n,m,ed,as;
int main(){
cin>>n>>m>>ed;
for(ri int i=1,u,v;i<=ed;++i){
cin>>u>>v;add(u,v,i);
}
for(ri int i=1;i<=n;++i){
as+=have_cp(i,i);
}
cout<<as;
return 0;
}