【2018五一清北培训】【2】【二分图以及匈牙利算法】

• 2020/3/27 upd：几乎重写了整份题解，只保留了原题解的图示部分。重写了一份能看的代码。

Task

给定一张二分图，其左部点集大小为 n，右部点集大小为 m，请求出其最大匹配。

Algorithm

首先说明几个概念。

• 一张图 G 是二分图当且仅当 G 的点集 V 可以分为两个点集 V_0, V_1，满足 V_0 \cup V_1 = V，V_0 \cap V_1 = \emptyset，且对于 G 的每条边 e，其两个端点分别属于不同的点集。

  用自然语言来描述就是，一张图是二分图，当且仅当它的点可以被分成两部分，而这张图上的所有边的两个端点，都分属不同的部分。

  我们称这两个点集，一个叫左部，一个叫右部。左部中的点叫左部点；右部中的点叫右部点。

• 图 G 的一个匹配是 G 的一个边集 E_0，满足 E_0 中的所有边都没有公共端点。

  用自然语言来描述就是，一张图的一个匹配是一些没有公共端点的边。

  可以想象，对于一个二分图而言，显然一个匹配是对于每一个左部点，连一条边向一个右部点，或者不向右部点连边。但是每个左部点不会对应两个或以上的右部点。

常用的二分图匹配算法是匈牙利算法，其正确性基于 hall 定理，本质是不断寻找增广路来扩大匹配数。但是其正确性证明比较复杂，在此略去。

匈牙利算法的过程是，枚举每一个左部点 u ，然后枚举该左部点连出的边，对于一个出点 v，如果它没有被先前的左部点匹配，那么直接将 u 匹配 v，否则尝试让 v 的“原配”左部点去匹配其他右部点，如果“原配”匹配到了其他点，那么将 u 匹配 v，否则 u 失配。

尝试让“原配”寻找其他匹配的过程可以递归进行。需要注意的是，在一轮递归中，每个右部点只能被访问一次。

算法的时间复杂度为 O(n \times e + m)，其中 n 是左部点个数，e 是图的边数，m 是右部点个数。

不难发现其实交换左右部点后的最大匹配数是一样的，而对于 m < n，有 m \times e + n < n \times e + m。所以有一个小 trick 是当右部点的个数比左部点多的时候，交换左右部能有更高的效率。

下面是喜 闻 乐 见的算法图示。

（图一）

在图一中，每个人物代表一个点，连线代表可以处的 cp（即可以进行的匹配）。

现在进行第一步： （图二）

在图二中，我们优先满足左侧标号小的点（男一黄少天）的期望 cp，于是我们把黄少和安康鱼（芙蕾雅）连在一起，已经匹配的边染成蓝色。

现在进行第二步： （图三）

在图三中，我们满足男二叶修的匹配，非常尴尬的是叶修也喜欢安康鱼，于是叶修绿了少天额不对，反正我们把叶修和安康鱼匹配在一起，少天表示没事我还有和泉纱雾，于是我们把少天的匹配改为和泉纱雾。

现在进行第三步： （图四）

在图四中，张新杰表示安康鱼蛮好看的啊，于是张新杰匹配到了安康鱼，而叶修匹配到了初音。

再来看男四 孙翔（真的不是我针对他emmm）

孙翔也喜欢安康鱼（emm安康鱼怎么这么受欢迎）他想让张新杰换一个匹配，但是张新杰不答应：我给你让了我就没 cp 了诶，所以不给。

于是孙翔失配了。

以上就是匈牙利算法的过程。不难发现，匈牙利算法就是一个绿与被绿协商与匹配的过程。

所以这张图的最大匹配为 3。

观察图可以得出：

1. 如果后来的和以前的发生矛盾，则以前的被绿优先退让。
2. 如果以前的退让之后没有cp可处，则以前的拒绝退让，新来的去寻找下一个匹配。
3. 如果新来的谁也匹配不上了，那就这么单着吧。

以上，就是匈牙利算法的全部内容

Code

#include <cstdio>
#include <vector>

const int maxn = 1005;

int n, m, t;
int mch[maxn], vistime[maxn];

std::vector<int> e[maxn];

bool dfs(const int u, const int tag);

int main() {
  scanf("%d %d %d", &n, &m, &t);
  for (int u, v; t; --t) {
    scanf("%d %d", &u, &v);
    e[u].push_back(v);
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) if (dfs(i, i)) {
    ++ans;
  }
  printf("%d\n", ans);
}

bool dfs(const int u, const int tag) {
  if (vistime[u] == tag) return false;
  vistime[u] = tag;
  for (auto v : e[u]) if ((mch[v] == 0) || dfs(mch[v], tag)) {
    mch[v] = u;
    return true;
  }
  return false;
}

另外，二分图匹配可以使用 dinic 算法，将复杂度降低至O(n~\sqrt e)。具体的，建立超级源点和超级汇点，源点向左侧连边，右侧向汇点连边。左右之间连边。上述边的流量都是 1 。由于 s 到点左侧任意一点 u 的流量是1，所以 u 最多被选择一次。同理右边的点也最多被选择一次。于是这个图的网络最大流即为该二分图的最大匹配。