二分图匹配

首先我们引入二分图的定义:顶点集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【模板】二分图匹配

发表评论

电子邮件地址不会被公开。 必填项已用*标注