题目描述
XX酒店的老板想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等，也有自己所爱的菜，但是该酒店只有p间房间，一天只有固定的q道不同的菜。
有一天来了n个客人，每个客人说出了自己喜欢哪些房间，喜欢哪道菜。但是很不幸，可能做不到让所有顾客满意（满意的条件是住进喜欢的房间，吃到喜欢的菜）。
这里要怎么分配，能使最多顾客满意呢？
输入输出格式
输入格式：
第一行给出三个正整数表示n,p,q(<=100)。
之后n行，每行p个数包含0或1，第i个数表示喜不喜欢第i个房间（1表示喜欢，0表示不喜欢）。
之后n行，每行q个数，表示喜不喜欢第i道菜。
输出格式：
最大的顾客满意数。
输入输出样例
题解
这是道三倍经验题。
对人拆点，设为$x_1,x_2$。
从$S$往每个房间连边，容量为$1$。
从每个房间往喜欢它的$x_1$连边，容量为$1$。
从每个$x_1$往对应的$x_2$连边，容量为$1$。（限流
从每个$x_2$往他喜欢的菜连边，容量为$1$。
最后从每道菜往$T$连$1$，跑最大流就是答案了。
/*
qwerta
P1402 酒店之王
Accepted
100
代码 C++，1.69KB
提交时间 2018-10-13 10:38:07
耗时/内存
34ms, 796KB
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct emm{
int e,f,v;
}a[];
int h[];
int tot=;
void con(int x,int y,int ds)
{
a[++tot].f=h[x];
h[x]=tot;
a[tot].e=y;
a[tot].v=ds;
a[++tot].f=h[y];
h[y]=tot;
a[tot].e=x;
return;
}
queue<int>que;
int d[];
int s,t;
inline bool bfs()
{
memset(d,,sizeof(d));
d[s]=;que.push(s);
while(!que.empty())
{
int x=que.front();que.pop();
for(int i=h[x];i;i=a[i].f)
if(!d[a[i].e]&&a[i].v)
{
d[a[i].e]=d[x]+;
que.push(a[i].e);
}
}
return d[t];
}
int dfs(int x,int al)
{
if(x==t||!al)return al;
int fl=;
for(int i=h[x];i;i=a[i].f)
if(d[a[i].e]==d[x]+&&a[i].v)
{
int f=dfs(a[i].e,min(al,a[i].v));
if(f)
{
fl+=f;
al-=f;
a[i].v-=f;
a[i^].v+=f;
if(!al)break;
}
}
if(!fl)d[x]=-;
return fl;
}
int main()
{
//freopen("a.in","r",stdin);
int n,p,q;
scanf("%d%d%d",&n,&p,&q);
s=,t=*n+p+q+;
for(int i=;i<=p;++i)
con(s,i,);
for(int i=;i<=n;++i)
{
for(int j=;j<=p;++j)
{
int x;
scanf("%d",&x);
if(x)
con(j,i+p,);
}
}
for(int i=;i<=n;++i)
con(i+p,i+p+n,);
for(int i=;i<=n;++i)
{
for(int j=;j<=q;++j)
{
int x;
scanf("%d",&x);
if(x)
con(i+p+n,j+p+n+n,);
}
}
for(int i=;i<=q;++i)
con(i+p+n+n,t,);
int ans=;
while(bfs())ans+=dfs(s,);
cout<<ans;
return ;
}