洛谷 P1402 酒店之王

P1402

题目描述

XX酒店的老板想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等，也有自己所爱的菜，但是该酒店只有p间房间，一天只有固定的q道不同的菜。

有一天来了n个客人，每个客人说出了自己喜欢哪些房间，喜欢哪道菜。但是很不幸，可能做不到让所有顾客满意（满意的条件是住进喜欢的房间，吃到喜欢的菜）。

这里要怎么分配，能使最多顾客满意呢？

输入输出格式

输入格式：

第一行给出三个正整数表示n,p,q(<=100)。

之后n行，每行p个数包含0或1，第i个数表示喜不喜欢第i个房间（1表示喜欢，0表示不喜欢）。

之后n行，每行q个数，表示喜不喜欢第i道菜。

输出格式：

最大的顾客满意数。

输入输出样例

输入样例#1：

输出样例#1：

Solution：

吐槽一下这道题面，这不明摆着的教辅的组成那道题嘛，就输入不一样，其它思路没一点区别，不懂得去看我当时写的博客吧！（还有就是为什么这道题是紫题啊，教辅的组成都只是蓝题诶！～）

代码：

 1 #include<bits/stdc++.h>
 2 #define il inline
 3 using namespace std;
 4 const int N=5200,inf=23333333;
 5 int n,p,q,h[N],cnt=1,dis[N],ans,s,t=520;
 6 struct edge{
 7 int to,net,v;
 8 }e[N*4];
 9 il void add(int u,int v,int w)
10 {
11     e[++cnt].to=v,e[cnt].net=h[u],e[cnt].v=w,h[u]=cnt;
12     e[++cnt].to=u,e[cnt].net=h[v],e[cnt].v=0,h[v]=cnt;
13 }
14 queue<int>Q;
15 il bool bfs()
16 {
17     memset(dis,-1,sizeof(dis));
18     Q.push(s),dis[s]=0;
19     while(!Q.empty())
20     {
21         int u=Q.front();Q.pop();
22         for(int i=h[u];i;i=e[i].net)
23         if(dis[e[i].to]==-1&&e[i].v>0)dis[e[i].to]=dis[u]+1,Q.push(e[i].to);
24     }
25     return dis[t]!=-1;
26 }
27 il int dfs(int u,int op)
28 {
29     if(u==t)return op;
30     int flow=0,used=0;
31     for(int i=h[u];i;i=e[i].net)
32     {
33         int v=e[i].to;
34         if(dis[v]==dis[u]+1&&e[i].v>0)
35         {
36             used=dfs(v,min(op,e[i].v));
37             if(!used)continue;
38             flow+=used,op-=used;
39             e[i].v-=used,e[i^1].v+=used;
40             if(!flow)break;
41         }
42     }
43     if(!op)dis[u]=-1;
44     return flow;
45 }
46 int main()
47 {
48     scanf("%d%d%d",&n,&p,&q);
49     for(int i=1;i<=n;i++)add(i+p,i+n+p,1);
50     int x;
51     for(int i=1;i<=n;i++)
52         for(int j=1;j<=p;j++){
53             scanf("%d",&x);
54             if(x==1)add(j,i+p,1);
55         }
56     for(int i=1;i<=n;i++)
57         for(int j=1;j<=q;j++){
58             scanf("%d",&x);
59             if(x==1)add(i+p+n,j+p+n*2,1);
60         }
61     for(int i=1;i<=p;i++)add(s,i,1);
62     for(int i=1;i<=q;i++)add(i+p+n*2,t,1);
63     while(bfs())ans+=dfs(s,inf);
64     cout<<ans;
65     return 0;
66 }