题目描述
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 第一眼二分图匹配，第二眼网络流
写二分图吧，短嘛
分别匹配菜和酒店，都link到了答案+1，否则不作处理（回归上一次匹配状态）
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
inline int read() {
int x=,f=;
char c=getchar();
while(c<''||c>'') c=getchar();
while(c<=''&&c>='') x=x*+c-'',c=getchar();
return x*f;
}
int n,p,q;
const int maxn = ;
int link[maxn];
struct node{
int v,next;
}edge[maxn];
int used[maxn],head[maxn],num;
inline void add_edge(int x,int y) {
edge[++num].v=y;edge[num].next=head[x];head[x]=num;
}
bool link1(int x,int f,bool flag) {
for(int i=head[x];i;i=edge[i].next) {
int v=edge[i].v;
if(flag&&v<=n+p)continue;
if(!flag&&v>n+p)continue;
if(used[v]!=f) {
used[v]=f;
if(!link[v]||link1(link[v],f,flag)) {
link[v]=x;
return true;
}
}
}
return ;
}
int tmp[maxn];
int main() {
n=read(),p=read(),q=read();
for(int i=;i<=n;++i) {
for(int j=;j<=p;++j) {
if(read())add_edge(i,n+j);
}
}
for(int i=;i<=n;++i) {
for(int j=;j<=q;++j) {
if(read())add_edge(i,n+p+j);
}
}
int ans=;
for(int i=;i<=n;++i) {
for(int j=n+;j<=n+p;++j) tmp[j]=link[j];
if(link1(i,i,)) {
if(link1(i,i,)) ans++;
else for(int j=n+;j<=n+p;++j)link[j]=tmp[j];
}
}
printf("%d\n",ans);
return ;
}