题目描述
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=0,f=1; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar(); return x*f; } int n,p,q; const int maxn = 1007; 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 0; } int tmp[maxn]; int main() { n=read(),p=read(),q=read(); for(int i=1;i<=n;++i) { for(int j=1;j<=p;++j) { if(read())add_edge(i,n+j); } } for(int i=1;i<=n;++i) { for(int j=1;j<=q;++j) { if(read())add_edge(i,n+p+j); } } int ans=0; for(int i=1;i<=n;++i) { for(int j=n+1;j<=n+p;++j) tmp[j]=link[j]; if(link1(i,i,0)) { if(link1(i,i,1)) ans++; else for(int j=n+1;j<=n+p;++j)link[j]=tmp[j]; } } printf("%d ",ans); return 0; }