#P1402. 酒店之王

    ID: 402 远端评测题 1000ms 125MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>二分图最大流网络流福建省历届夏令营

酒店之王

题目描述

XX 酒店的老板想成为酒店之王,本着这种希望,第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等,也有自己所爱的菜,但是该酒店只有 pp 间房间,一天只有固定的 qq 道不同的菜,每个房间只能住一位客人,每道菜也只能给一位客人食用。

有一天来了 nn 个客人,每个客人说出了自己喜欢哪些房间,喜欢哪道菜。但是很不幸,可能做不到让所有顾客满意(满意的条件是住进喜欢的房间且吃到喜欢的菜)。

要怎么分配,能使最多顾客满意呢?

输入格式

第一行给出三个整数,分别表示表示 n,p,qn,p,q

之后 nn 行,每行 pp 个整数,只可能是 0011,第 ii 行第 jj 个数表示第 ii 个人喜不喜欢第 jj 个房间(11 表示喜欢, 00 表示不喜欢)。

之后 nn 行,每行 qq 个整数,只可能是 0011,第 ii 行第 jj 个数表示第 ii 个人喜不喜欢第 jj 道菜(11 表示喜欢, 00 表示不喜欢)。

输出格式

最大的顾客满意数。

2 2 2
1 0
1 0
1 1
1 1
1

提示

数据规模与约定

对于全部的测试点,保证 1n,p,q1001 \leq n,p,q \leq 100