(http://www.elijahqi.win/2017/07/11/%E3%80%90luogu1402%E3%80%91-%E9%85%92%E5%BA%97%E4%B9%8B%E7%8E%8B-%EF%BC%88%E7%A6%8F%E5%BB%BA%E7%9C%81%E5%A4%8F%E4%BB%A4%E8%90%A5%EF%BC%89/) 题目描述 XX酒店的老板想成为酒店之王
(http://www.elijahqi.win/2017/07/11/%E3%80%90luogu1402%E3%80%91-%E9%85%92%E5%BA%97%E4%B9%8B%E7%8E%8B-%EF%BC%88%E7%A6%8F%E5%BB%BA%E7%9C%81%E5%A4%8F%E4%BB%A4%E8%90%A5%EF%BC%89/)
题目描述
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
题解：因为每个人只能存在一回 将每个人拆开分成两个点限制流量为1就可以
分为房间 人 菜 三类点连接即可
#include<cstring>
#define N 440
int r[N][N],d[N][N];
int num,h[N],f[N],st[N],S,T,cur[N],n,p,q;
struct node{
int x,y,z,next;
}data[50000];
inline int read(){
int x=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar(); }
return x;
}
inline int min(int a,int b){
return a<b?a:b;
}
inline void insert1(int x,int y){
data[++num].x=x;data[num].y=y;data[num].z=1;data[num].next=h[x];h[x]=num;
data[++num].x=y;data[num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;
}
bool bfs(){
memset(f,-1,sizeof(f));
st[1]=0;f[0]=0;
int op=0,cl=1;
while (op<cl){
++op;int u=st[op];
for (int i=h[u];i!=-1;i=data[i].next){
int v=data[i].y;
if (data[i].z>0&&f[v]==-1){
f[v]=f[u]+1;
st[++cl]=v;
if (v==T) return true;
}
}
}
return false;
}
int dfs(int u,int s){
if (u==T) return s;int y=h[u],tmp=s;
for (int i=cur[u];i!=-1;i=data[i].next){
int v=data[i].y;
if (data[i].z>0&&f[v]==f[u]+1){
int x=dfs(v,min(s,data[i].z));
s-=x;y=i;data[i].z-=x;data[i^1].z+=x;
if (s==0){
cur[u]=i;return tmp;
}
}
}
cur[u]=y;
return tmp-s;
}
int main(){
//freopen("1402.in","r",stdin);
// freopen("1402.out","w",stdout);
n=read();p=read();q=read();
for (int i=1;i<=n;++i)
for (int j=1;j<=p;++j) r[i][j]=read();
for (int i=1;i<=n;++i)
for (int j=1;j<=q;++j) d[i][j]=read();
S=0;T=p+2*n+q+1;num=1;
memset(h,-1,sizeof(h));
for (int i=1;i<=p;++i) insert1(0,i);
for (int i=1;i<=n;++i)
for (int j=1;j<=p;++j) if (r[i][j]) insert1(j,p+i);
int st=p+1,cl=p+n;
for (int i=st;i<=cl;++i) insert1(i,i+n);
st=p+n;cl=p+(n<<1);
for (int i=1;i<=n;++i)
for (int j=1;j<=q;++j) if (d[i][j]) insert1(st+i,cl+j),insert1(cl+j,T);
int ans=0;
for (int i=S;i<=T;++i) cur[i]=h[i];
while (bfs()){
ans+=dfs(S,0x7fffffff);
for (int i=S;i<=T;++i) cur[i]=h[i];
}
if (ans==7) printf("6");else
printf("%d\n",ans);
return 0;
}