首页 > 代码库 > 洛谷P1402 酒店之王(二分图)
洛谷P1402 酒店之王(二分图)
P1402 酒店之王
题目描述
XX酒店的老板想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等，也有自己所爱的菜，但是该酒店只有p间房间，一天只有固定的q道不同的菜。
有一天来了n个客人，每个客人说出了自己喜欢哪些房间，喜欢哪道菜。但是很不幸，可能做不到让所有顾客满意（满意的条件是住进喜欢的房间，吃到喜欢的菜）。
这里要怎么分配，能使最多顾客满意呢？
输入输出格式
输入格式：
第一行给出三个正整数表示n,p,q(<=100)。
之后n行，每行p个数包含0或1，第i个数表示喜不喜欢第i个房间（1表示喜欢，0表示不喜欢）。
之后n行，每行q个数，表示喜不喜欢第i道菜。
输出格式：
最大的顾客满意数。
输入输出样例
输入样例#1：
2 2 21 01 01 11 1输出样例#1：
1
/*其实很简单，做两个二分图即可。可以构造两个二分图，依次从某一个客人出发同时对两个二分图寻找增广路若对某一个二分图没有找到增广路，则恢复从该客人出发找到的所有增广路(这条不行)，反之，则改进匹配。*/#include<iostream>#include<cstdio>#include<cstring>#define N 101using namespace std;int n,p,q,i,j,RL[N][N],FL[N][N],LB[N],book[N],answer,eat[N];bool CR[N],visR[N],visF[N],LCR[N],CF[N];bool room_(int No){ for (int i=1; i<=n; i++) if (RL[No][i]&&!visR[i]) { visR[i]=1; if (book[i]==0||room_(book[i])) { CR[No]=1; book[i]=No; return 1; } } return 0;}bool food_(int No){ for (int i=1; i<=n; i++) if (FL[No][i]&&!visF[i]) { visF[i]=1; if (eat[i]==0||food_(eat[i])) { CF[No]=1; eat[i]=No; return 1; } } return 0;}int main (){ scanf("%d%d%d",&n,&p,&q); for (i=1; i<=n; i++) for (j=1; j<=p; j++) scanf("%d",&RL[i][j]); for (i=1; i<=n; i++) for (j=1; j<=q; j++) scanf("%d",&FL[i][j]); while (1) { for (i=1; i<=n; i++) if (!CR[i]) { for (j=1; j<=n; j++) visR[j]=0; for (j=1; j<=n; j++) visF[j]=0; for (j=1; j<=n; j++) LCR[j]=CR[j]; for (j=1; j<=n; j++) LB[j]=book[j]; if (room_(i)&&food_(i)) { answer++; continue; } else//因为无法匹配所以取消上次所有增广 { for (j=1; j<=n; j++) CR[j]=LCR[j]; for (j=1; j<=n; j++) book[j]=LB[j]; } } break; } printf("%d\n",answer); return 0; return 0; return 0;}
洛谷P1402 酒店之王(二分图)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。