二分图匹配
概念和定义部分可参考Renfei Song大佬的图文博客
我觉得一大块的关于二分图的定义还是看原博客好一些，以下是部分引用
不过说真的，概念这种东西要是没有人讲，全靠自己看的话有些烦人
第一部分：简单的dfs匈牙利算法
关于匈牙利算法的一些概念：
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。例如，图 5 中的一条增广路如图 6 所示（图中的匹配点均用红色标出）：
增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点（类似于贪心思想）。找不到增广路时，达到最大匹配（这是增广路定理）。匈牙利算法正是这么做的。
我在看二分图匹配题解的时候看到了这样一句话：
@constructor: 因为（图）是对称的。根据交叉路原理容易证明每一条增广路的起点和终点分属不同点集（因为在从偶数次所到位置的下一次一定走匹配边，这意味着这一定找不到未盖点。）
所以从增广路定义出发，我们可以每一次都在同一点集里找增广路
我的个人理解：匈牙利算法是基于搜索和贪心的角度来通过增广路的定义进行优化的查找方式
dfs版本代码：
#include <cstdio>
#include <cstring>
const int maxn=1000+10;
int n,m,e;
int tot=0;
bool vis[maxn];
bool valid[maxn][maxn];
int match[maxn];
void AddEdge()
{
scanf("%d%d%d",&n,&m,&e);
int u,v;
while(e--)
{
scanf("%d%d",&u,&v);
if (u<=n&&v<=m)
valid[u][v]=1;
}
}
bool dfs(int pos)
{
for (int i=1;i<=m;i++)
if (!vis[i]&&valid[pos][i])
{
vis[i]=1;
if (!match[i]||dfs(match[i]))//如果当前考虑的点还未配对或者它配对的点仍然可以和别的点配对
{
match[i]=pos;//配对
return 1;//找到可供配对的，直接返回
}
}
return 0;//不能在另一个点集里找到匹配点使匹配边增加
}
int main()
{
AddEdge();
int ans=0;
for (int i=1;i<=n;i++)
{
if (dfs(i))
ans++;
memset(vis, 0, sizeof(vis));
}
printf("%d\n",ans);
return 0;
}第二部分：没那么简单但是更快的Dinic算法
首先，为什么二分图匹配可以用网络最大流来做呢？
二分图中，我们要找的是最大匹配。也可以理解为：所有边的容量为1，当且仅当一条边连接两个点集中的点不被别的边相连，流量达到最大（感性理解一下！我语文不好）。所以我们只要虚设出一个源点和一个汇点，在二分图上跑网络最大流就可以了。同时因为Dinic是同时找多条增广路的，所以跑得飞快