二分图匹配(最大匹配：匈牙利算法) 前言 相关芝士
前些时间康了一下染色法判定二分图的板子，那今天就来说说关于二分图的另外一个算法：
匈牙利算法。
相关芝士
简单介绍一下概念。
二分图，就是能（把图中的点分为(U,V)两个集合，且图中的边只在(U,V)之间出现）的图。也就是对于分出的集合来说，集合内部不能有边。能分出来的图就是二分图。
另外的一种定义是：不含有「含奇数条边的环」的图。
比如这是一张二分图：
但是我们一般将其明显表示为二分图，就把两个集合的点放置在两边，就像这样：
以上。
匹配，即一个边的集合，在这个边的集合中，任意两条边都没有公共顶点。比如下图中的蓝边就是一个[匹配]。
懂了匹配的概念，还要引入几个浅显的概念：匹配点，匹配边，未匹配点，非匹配边。
匹配点就是由这个匹配（一定要记住“匹配”是一个边的集合）中的边所连起来的点，没有被连起来的就是未匹配点。匹配边和非匹配边同理。
最大匹配，所有的匹配中，所包含的边数最多的匹配。
补充概念：我也不懂
完美匹配，即每个左边集合中的点都可以通过匹配中的边找到一个唯一的右边集合中的点。当然，当所有点都是匹配点的时候，这个匹配就是一个完美匹配。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替 路称为增广路（agumenting path）。
下图的蓝边就是一个完美匹配的例子：
以上就是要了解的基本概念。（二分图，匹配，匹配点，匹配边，未匹配点，非匹配边，最大匹配）
匈牙利算法，就是来解决求最大匹配包含的边的数量的算法。
让我们来通过实例（真）感性地理解一下算法流程。
以这个图片为例：
为了形象，我们把左边的点看做男孩们，右边的点就是女孩们，连边表示他们互相有好感海王出来挨打。现在要让你当这个月老，凑更多的cp祸害人间。
模拟开始！
首先来给男孩1找对象，首先找到女孩5，发现她没有被匹配，于是暂时让他们成为一对，并且记录现在女孩5的对象是男孩1.
然后就轮到男孩2了。很可惜，他所钟意的女孩5已经被暂时选中了，但是不能怂啊，于是我们找到女孩5的对象男孩1，让他试试能不能换一个（是的没错），然后发现男孩1可以匹配女孩6，那么就把1和6匹配起来，5就归2了。
这不是一个悲伤的故事
男孩3顺利匹配到名花无主的女孩8.
最后一个男孩4所连向的女孩5也已经被选中了，那这次我们再去看看原配2能不能换一个（霸气），但是非常悲伤的是，2已经走投无路莫得选择了，所以男孩4很遗憾地失配了。
所以这张图中的最大匹配就是上图中的三条边。
模拟结束
可以发现，在这个找妹子的过程中，我们始终坚持能让就让，这就是匈牙利算法的核心思想。
另外，对于这个腾位置的过程也是递归的，比如回去找到原配要求换的过程中，可能还会牵扯到另外的一些调整关系（就是乱）
代码部分
int pre[510];
//[已经确定被匹配]的点的前驱
bool vis[510];
//在[当前尝试的匹配]中被选中的标记
//尝试加入点u看是否能合理调整之后让匹配中边数更多
bool find(int u)
{
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(!vis[v])
{
vis[v]=1;
if(!pre[v]||find(pre[v]))
{
pre[v]=u;
return true;
}
}
}
return false;
}
在递归过程中其实也进行了腾位，具体可以请读者自行模拟一下我懒就不给大家画了（咕了）