【洛谷1402】酒店之王

题面

题目描述

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

题解

看起来，这道题就像是一道二分图匹配。 然而我一开始想得太简单。。。。 直接把菜和房间连线去匹配。。。 明显是错的。。

如果只有菜或者只有房间 那么这道题就是裸的二分图匹配（直接匈牙利就行了） 但是，现在存在两个元素。 —-那就做两次二分图匹配嘛。。。。

值得注意的是，如果在匹配第一个元素的时候成功，但是在匹配第二个元素的时候失败，要把第一个元素的匹配进行一次恢复。（自己想想为什么）

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int MAX=110; vector<int> e1[MAX],e2[MAX]; int match1[MAX],match2[MAX]; bool vis[MAX]; int Copy[MAX]; bool used[MAX]; int n,q,p; int k,ans=0; bool DFS1(int x) { int v; for(int i=0;i<e1[x].size();++i) { v=e1[x][i]; if(!vis[v]) { vis[v]=true; if(!match1[v]||DFS1(match1[v])) { used[v]=true; Copy[v]=match1[v]; match1[v]=x; return true; } } } return false; } bool DFS2(int x) { int v; for(int i=0;i<e2[x].size();++i) { v=e2[x][i]; if(vis[v])continue; vis[v]=true; if(!match2[v]||DFS2(match2[v])) { match2[v]=x; return true; } } return false; } int main() { cin>>n>>p>>q; for(int i=1;i<=n;++i) { for(int j=1;j<=p;++j) { scanf("%d",&k); if(k)e1[i].push_back(j); } } for(int i=1;i<=n;++i) { for(int j=1;j<=q;++j) { scanf("%d",&k); if(k)e2[i].push_back(j); } } for(int i=1;i<=n;++i) { memset(vis,0,sizeof(vis)); memset(used,0,sizeof(used)); if(DFS1(i)) { memset(vis,0,sizeof(vis)); if(DFS2(i)) ++ans; else for(int j=1;j<=p;++j) if(used[j]) match1[j]=Copy[j]; } } cout<<ans<<endl; return 0; }