Matching

图里的match是边的集合M，要求M里没有两个边是有公共顶点的。这个名字可能是起源于婚姻问题，如果有公共顶点就是重婚了，所以是不允许的。

Marriage Problem: $m$个男孩，每个男孩认识一些女孩，现在开始match，要求每个男孩必须和他认识的女孩结婚，求这种方法存在的充分必要条件。

Hall's Theorem: Marriage Problem有解的充要条件是，任取$k$个男孩，他们必须认识至少$k$个女孩，其中$1\leq k\leq m$

二分图的最大match可以用网络流里面的Augmenting path来解决，先回顾一下网络流里的一些概念。

Residual network：对于一个网络上的flow来说，Residual network记录了这个flow在不违反网络每个路径的流量限制的条件下的所有变化的自由度。而且Residual network上的flow和原来的flow叠加还是原网络的一个合法的flow，满足flow的三个约束。

Augmenting path：是Residual network上的一个从源头到终点的简单路径。

augmenting path的residual capacity：是这个augmenting path上在Residual network里允许的最大流量。

二分图的最大match

所以Augmenting path不过是有向图的一个简单路径，所以用BFS或DFS查找均可。

二分图的最大match是这样转换为最大流问题的，首先男孩那边加一个节点$s$作为源头，并且和所有的男孩相连，女孩这边加一个节点作为终点$t$，同样和所有女孩相连，男孩到女孩的所有边都是男孩指向女孩。每条边的容量都设置为1。

很显然最后的flow不会有两个男孩连接到一个女孩，否则从这个女孩到$t$的流量就为2，这是不可能的。假设起始的时候flow的流量为0，每找到一个Augmenting path，这个path的容量只能是1。

用DFS找Augmenting path的时候，可以直接遍历所有男孩，因为这就相当于遍历所有$s$的邻居。

考虑两种Augmenting path，最简单的情况是，从某男出发，第一步就发现一个没被match的女孩，得一条边的Augmenting path；如果从某男开始DFS遇到的第一个女孩已经match了，这时候DFS不能停，因为按Residual network的容量看，这女孩到和她match的男孩的路径有一个反向的容量，所以继续，坏的情况，这男孩只认识这一个女孩，这时候DFS要开始返回了，这条path不是Augmenting path，好的情况，这男孩还认识其他没match的女孩，DFS会访问到这个新没match的女孩，这时候我们就得到了一条Augmenting path。

第二种情况实际上是劝说一个已经match的男孩换女朋友。

程序是这样的，bpm(u)可以理解为给u找女朋友，如果发现的女孩已有男朋友，劝说其男朋友换女朋友，而且不能换DFS已经见过的女孩，既然让人家换就得给人家找所有要再调bpm。

算法最终返回的条件是发现一个新的没match的女孩，而且这时候所有Augmenting path的男孩都得换女朋友。