二分图匹配

首先我们引入二分图的定义：顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

然后我们就可以发现二分图一个神奇的性质：不存在长度为奇数的环，这个可以用反证法证明（虽然好像没有什么用）。

接下来我们再引入几个定义：

匹配：一个匹配是一个边的集合，其中任意两条边都没有公共顶点。

最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。完美匹配一定是最大匹配，但并非每个图都存在完美匹配。

对于求二分图的最大匹配的问题，我们可以采用网络流或匈牙利算法，网络流算法十分显然就是在图的左右两侧分别建立源点和汇点，不过这个算法并不是这篇博客要介绍的内容。这里介绍的是专门的求二分图最大匹配的匈牙利算法。

匈牙利算法的流程和网络流类似，就是一个不断寻找增广路的过程。对于一个未匹配节点，如果我们从它出发，依次走未匹配边、匹配边、未匹配边，如果经过了一个未匹配点，那么显然我们可以将我们走过的边的状态进行交换，这样就可以使匹配的个数多1。

同时我们还可以发现一个性质：如果一个点进行过一次增广后，就不会再进行增广了。因为如果一个点从匹配点变为了未匹配点，显然是因为将它匹配并不是最优点。

然后我们就解决了匈牙利算法的流程：首先将二分图的点分为两个集合，集合之中的点两两没有连边，然后对一边的点进行扫描，只要当前节点还没有增广过且未被匹配，就进行一次增广。增广的过程直接使用dfs或bfs寻找增广路，只要找到一个增广路就退出即可。从这里我们也可以看出匈牙利算法的复杂度为O(VE)。

下面上代码：

bool dfs(int k, int t)
{
    int d = head[k];
    while (d)
    {
        if (vis[a[d].v] != t)
        {
            vis[a[d].v] = t;
            if (!mch[a[d].v] || dfs(mch[a[d].v], t))
            {
                mch[a[d].v] = k;
                return true;
            }
        }
        d = a[d].next;
    }
    return false;
}
//a为邻接表
//mch记录的是一个集合内的点匹配的是哪一个另一个侧集合内的点
//vis数组记录的是一个点在第t次增广中是否被搜索过

推荐例题：洛谷P3386【模板】二分图匹配