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分析：
最大流裸题 分三类点:房间.人.菜 源点想每个房间连边，如果第i人喜欢第j间房，第j间房向第i人连边， 针对每个人拆点，自己连向自己，保证人只有一个（限制流量）， 如果第i人喜欢第j道菜，第i人向第j道菜连边，每道菜向汇点连边。 边的容量均为1.然而，一开始naive的我是这么建图的：
源点向每个人连边，每个人向喜爱的房间连边，把房间拆点，自己连向自己（限制流量） 第i人喜爱的所有房间都分别向第i人喜欢的菜连边，每道菜向汇点连边。 只有20分QAQ，而且这么处理在房间向菜品连边时很麻烦，边的数量很多。。。这里写代码片#include#include #include #include using namespace std;const int INF=10000010;const int N=1100;struct node{ int x,y,v,next;};node way[N*100];int n,p,q,kaishi,jieshu;int fj[N][N],st[N],tot=-1,deep[N];void add(int u,int v,int z){ tot++; way[tot].x=u;way[tot].y=v;way[tot].v=z;way[tot].next=st[u];st[u]=tot; tot++; way[tot].x=v;way[tot].y=u;way[tot].v=0;way[tot].next=st[v];st[v]=tot; return;}int bfs(int s,int t){ int i; memset(deep,0x7f,sizeof(deep)); queue q; bool p[N]; memset(p,1,sizeof(p)); q.push(s); deep[s]=1; p[s]=0; while (!q.empty()) { int r=q.front(); q.pop(); for (i=st[r];i!=-1;i=way[i].next) { if (way[i].v&&p[way[i].y]) { q.push(way[i].y); deep[way[i].y]=deep[r]+1; p[way[i].y]=0; } } } return deep[t]<0x7f;}int dfs(int now,int t,int limit){ if (now==t||limit==0) return limit; int f,flow=0; int i; for (i=st[now];i!=-1;i=way[i].next) { if (deep[way[i].y]==deep[now]+1&&(f=dfs(way[i].y,t,min(limit,way[i].v)))) { flow+=f; limit-=f; way[i].v-=f; way[i^1].v+=f; if (!limit) break; } } return flow;}int dinic() //模板 { int ans=0; while (bfs(kaishi,jieshu)) ans+=dfs(kaishi,jieshu,INF); return ans;}int main(){ scanf("%d%d%d",&n,&p,&q); memset(st,-1,sizeof(st)); kaishi=0; jieshu=n+p+q+n+1; for (int i=1;i<=n;i++) { add(i+p,i+p+n,1); //自己向自己连边 for (int j=1;j<=p;j++) { if (i==1) add(0,j,1); //源点向房间连边 int u; scanf("%d",&u); //第i个人喜欢第j个房间 if (u) add(j,i+p,1); } } for (int i=1;i<=n;i++) { for (int j=1;j<=q;j++) { if (i==1) add(j+p+n+n,jieshu,1); //菜品向汇点连边 int u; scanf("%d",&u); if (u) add(i+p+n,j+p+n+n,1); //人向菜品连边 } } printf("%d",dinic()); return 0;}