二分图

二分图的概念：

• 如果将一个无向图的结点染成黑色或白色，并且可以满足任意相同颜色的两点之间没有边，这个无向图就是二分图。

一个图是否为二分图，一般用染色法判断。用 \(0,1\) 表示顶点的颜色。将任意一个顶点任意染色，然后遍历图，如果遇到没染色的点，就染成与这个点相反的颜色；否则判断是否与这个点颜色不同，如果颜色相同则不为二分图。

我们将一种颜色的点放到左侧，其他点放到右侧。这样所有边都连接异侧的点。

二分图匹配问题

二分图匹配：

在所有边中选择一些，满足每个点最多连一条边，这个边集即为一个匹配。

二分图最大匹配

在所有匹配中，边数最多的即为最大匹配。

求二分图最大匹配一般有两种算法：最大流、匈牙利算法。下面分别讲解。

1. 最大流

建一个源点，向所有左侧的点连一条流量为 \(1\) 的边，代表点只能连一条边；建一个汇点，所有右侧的点向汇点连一条流量为 \(1\) 的边。中间的边由左边连向右边，流量为 \(1\)。这个图的最大流即为最大匹配边数。

共有 \(N\) 个点，\(M\) 条边，求解最大流，时间复杂度上界为 \(\mathcal{O}(N^2M)\)，但实际上远远达不到上界。

例题 洛谷-P3386/HDU-2063

这里用 ISAP 算法求最大流。下面给出代码：

代码

2. 匈牙利算法

在学习该算法时，一定要注意各个定义是左边的点还是右边的点。

设 \(match_i\) 表示右侧的点 \(i\) 当前所匹配到左侧的点。

遍历所有左侧的点 \(u\)，然后遍历右侧的点 \(v\)，如果满足一下两个条件之间的一个，就将 \(match_v\) 改为 \(u\)，并让匹配数加 \(1\)。

• \(v\) 还没有匹配左侧的点

• 成功为 \(v\) 找到了一个新的匹配

设 \(dfs(u)\) 表示为左侧点 \(u\) 找匹配，如果成功返回 \(1\)，否则返回 \(0\)。

每次搜索时，我们再设一个 \(vs\) 数组，\(vs_i\) 表示右侧点 \(i\) 是否被遍历过，保证不重复遍历。

接下来遍历 \(u\) 连接到的所有点 \(v\)，如果 \(match_v=0\) 或者 \(dfs(match_v)=1\)，则将 \(match_v\) 改为 \(u\) 并返回 \(1\)。如果没有任何点能够匹配，返回 \(0\)。

这样左侧每个点匹配时，最多会把所有边遍历一遍，因此时间复杂度为 \(\mathcal{O}(NM)\)。

代码

两种算法的比较

以洛谷数据为参照，下面是两种算法的对比：

读者可根据情况自行选择算法。