题目描述

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

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

这里要怎么分配，能使最多顾客满意呢？

输入输出格式

输入格式：

第一行给出三个正整数表示n,p,q(<=100)。

之后n行，每行p个数包含0或1，第i个数表示喜不喜欢第i个房间（1表示喜欢，0表示不喜欢）。

之后n行，每行q个数，表示喜不喜欢第i道菜。

输出格式：

最大的顾客满意数。

输入输出样例

输入样例#1：

2 2 2
1 0
1 0
1 1
1 1

输出样例#1：

1

思路：正解是最大流，但是我不会……那怎么办呢？？？其实，这道题亦可用二分图做。怎么个分法呢？我们发现，如果说一个人喜欢一个房间的同时也喜欢这个房间里的菜的话，那这个题就是裸的二分图最大匹配了，对吧？但是，这道题，并不是，而是如果有一个不喜欢，那就不能匹配，那我们可以建两个二分图啊，对不对？如果两个二分图都能够匹配，则\(ans\)++，但是不能呢？我们发现，我们\(dfs\)找增广路的时候，\(link\)数组是会影响到后面的状态的，所以如果一个人无法匹配一个房间，我们要把\(link\)数组还原，额外开两个数组记录就可以解决了。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define maxn 207
using namespace std;
int n,p,q,link[maxn][2],num,zrj,head1[maxn],a[maxn],b[maxn],cnt,head2[maxn];
bool vis1[maxn],vis2[maxn];
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct node {
  int v,nxt;
}e1[maxn*maxn],e2[maxn*maxn];
inline void ct1(int u, int v) {
  e1[++num].v=v;
  e1[num].nxt=head1[u];
  head1[u]=num;
}
inline void ct2(int u, int v) {
  e2[++cnt].v=v;
  e2[cnt].nxt=head2[u];
  head2[u]=cnt;
}
bool dfs1(int u) {
  for(int i=head1[u];i;i=e1[i].nxt) {
    int v=e1[i].v;
    if(!vis1[v]) {
      vis1[v]=1;
      if(!link[v][0]||dfs1(link[v][0])) {
        link[v][0]=u;
        return 1;
      }
    }
  }
  return 0;
}
bool dfs2(int u) {
  for(int i=head2[u];i;i=e2[i].nxt) {
    int v=e2[i].v;
    if(!vis2[v]) {
      vis2[v]=1;
      if(!link[v][1]||dfs2(link[v][1])) {
        link[v][1]=u;
        return 1;
      }
    }
  }
  return 0;
}
int main() {
  n=qread(),p=qread(),q=qread();
  for(int i=1;i<=n;++i) {
    for(int j=1,x;j<=p;++j) {
      x=qread();
      if(x) ct1(i,j);
    } 
  }
  for(int i=1;i<=n;++i) {
    for(int j=1,x;j<=q;++j) {
      x=qread();
      if(x) ct2(i,j);
    } 
  }
  for(int i=1;i<=n;++i) {
    memset(vis1,0,sizeof(vis1));
    memset(vis2,0,sizeof(vis2));
    for(int j=1;j<=n;++j) a[j]=link[j][0],b[j]=link[j][1];
    if(dfs1(i)&&dfs2(i)) ++zrj;
    else for(int j=1;j<=n;++j) 
    link[j][0]=a[j],link[j][1]=b[j];
  }
  printf("%d\n",zrj);
  return 0;
}