#6345. 特殊三分图匹配

内存限制:256 MiB 时间限制:100 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Diogenes

题目描述

一般三分图的匹配需要运用基于拉格朗日松弛的分支定界法,并运用启发式算法得到较优的初始下界。已被证明是 NPC 问题。出题者在此说明一般三分图的匹配可以解决本题。
三个点集 X, Y, Z ,同一点集之间没有边, X,Z 点集之间没有边, X,Y 点集之间有边, Y,Z 点集之间有边。
求三分图的最大匹配。

注意:本题的一个匹配指的是 X 点集中的点 i Y 点集中的点 j , Z 点集中的点 k 被两条边相连。三分图最大匹配指的是满足上述条件的不相交点集 \{ i , j , k \} 的个数

输入格式

第 1 行五个整数 n_1,n_2,n_3,m_1,m_2
分别表示 X,Y,Z 点集的点数, X,Y 之间的边数, Y,Z 之间的边数。
然后 m_1 行,一行两个整数 a,b ,表示 x_a y_b 之间有边。
然后 m_2 行,一行两个整数 a,b ,表示 y_a 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

样例解释 1

一种最大匹配是:
X1 - Y1 - Z2
X2 - Y2 - Z1

数据范围与提示

输入可能存在重边。
对于 100\% 的数据, n_1,n_2,n_3 \leq 1000,m_1,m_2 \leq 5000