三分图最大匹配

题目描述

一般三分图的匹配需要运用基于拉格朗日松弛的分支定界法，并运用启发式算法得到较优的初始下界。已被证明是 NPC 问题。出题者在此说明一般三分图的匹配可以解决本题。

给定三个点集 $X, Y, Z$，满足：

• 同一点集之间没有边；
• 点集 $X$ 与 $Z$ 之间没有边；
• 点集 $X$ 与 $Y$ 之间有边，点集 $Y$ 与 $Z$ 之间有边。

求该三分图的最大匹配。

注意：本题中的一个匹配指的是由点集 $X$ 中的点 $i$、点集 $Y$ 中的点 $j$、点集 $Z$ 中的点 $k$ 组成的三元组，且满足 $i$ 与 $j$ 之间有边、$j$ 与 $k$ 之间有边。三分图的最大匹配指的是满足上述条件的不相交点集 $\{i, j, k\}$ 的最大个数（即任意两个匹配三元组没有公共点）。

输入格式

第一行包含五个整数 $n_1, n_2, n_3, m_1, m_2$，含义如下：

• $n_1$：点集 $X$ 的点数；
• $n_2$：点集 $Y$ 的点数；
• $n_3$：点集 $Z$ 的点数；
• $m_1$：点集 $X$ 与 $Y$ 之间的边数；
• $m_2$：点集 $Y$ 与 $Z$ 之间的边数。

接下来 $m_1$ 行，每行两个整数 $a, b$，表示点集 $X$ 中的点 $x_a$ 与点集 $Y$ 中的点 $y_b$ 之间有一条边。

最后 $m_2$ 行，每行两个整数 $a, b$，表示点集 $Y$ 中的点 $y_a$ 与点集 $Z$ 中的点 $z_b$ 之间有一条边。

输出格式

一行一个整数，表示该三分图的最大匹配数。

样例输入 1

3 4 5 6 6
1 1
1 3
2 2
2 4
3 1
3 3
1 2
2 1
2 3
3 2
4 4
4 5

样例输出 1

2

样例输入 2

3 3 3 5 4
1 2
2 3
2 2
1 3
3 1
1 2
3 3
3 2
2 1

样例输出 2

3

样例解释 2

一种最大匹配方案为：

• $X_1 - Y_1 - Z_2$
• $X_2 - Y_2 - Z_1$
• $X_3 - Y_3 - Z_3$

数据范围与提示

• 输入中可能存在重边（多条边连接同一对点，不影响匹配判断）；
• 对于 100% 的数据，满足 $n_1, n_2, n_3 \leq 1000$，$m_1, m_2 \leq 5000$。