[编程题]项目经理（二分图）

项目经理

参考, 模板

'''二分图, 匈牙利算法
最大匹配数: 最大匹配的匹配边的数目
最小点覆盖数: 选取最少的点, 使任意一条边至少有一个端点被选择
最大独立数: 选取最多的点, 使任意所选两点均不相连
最小路径覆盖数: 对于一个 DAG (有向无环图), 选取最少条路径, 使得每个顶点属于且仅属于一条路径. 路径长可以为 0 (即单个点)

定理1: 最大匹配数 = 最小点覆盖数 (这是 Konig 定理)
定理2: 最大匹配数 = 最大独立数
定理3: 最小路径覆盖数 = 顶点数 - 最大匹配数
'''

from collections import defaultdict


a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))
n = int(input().strip())

G = defaultdict(set)
for i in range(n):
    x, y = list(map(int, input().strip().split()))
    G[x].add(y)

maxn = 2000

# match: 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
# st: 表示第二个集合中的每个点是否已经被遍历过
st, match, ans = [False] * maxn, [-1] * maxn, 0

def find(x):
    for i in G[x]:
        if st[i] == False:
            st[i] = True
            if match[i] == -1 or find(match[i]):
                match[i] = x
                return True
    return False

for i in a:
    st = [False] * maxn
    if find(i): ans = ans + 1

print(ans)