Luogu 1402 酒店之王(二分图最大匹配)

时间:2022-06-16 06:28:57

Luogu 1402 酒店之王(二分图最大匹配)

Description

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

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

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

Input

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

之后n行,每行p个数包含0或1,第i个数表示喜不喜欢第i个房间(1表示喜欢,0表示不喜欢)。

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

Output

最大的顾客满意数。

Sample Input

2 2 2

1 0

1 0

1 1

1 1

Sample Output

1

Http

Luogu:https://www.luogu.org/problem/show?pid=1402

Source

二分图的最大匹配

题目大意

有两样东西需要匹配的二分图最大匹配问题

解决思路

这个题目首先要注意的地方就是只要当房间和菜都满意时,顾客才算满意。

我们平时做的二分图都是两个组进行匹配,这里突然来了三个组,怎么办呢?

其实三个的匹配从思路上与两个的匹配是一致的,依然使用的是匈牙利算法,核心思想还是“让”出位置来匹配。

关于匈牙利算法的基本思想,这里不再多说。(可以参考我的这三篇文章1 2 3)那么这个题,我们就建立两个二分图,一个是客人-房间,另一个是客人-菜。我们依然枚举每一个客人,首先判断其能否在客人-房间图中匹配成功,若能成功,再判断能否在客人-菜图中匹配成功。若都能匹配成功,则说明这个客人可以匹配。但若在客人-菜图中匹配失败,此时要回去把客人-房间图中修改的内容改回去。

在笔者的代码中,我们用带_room的表示客人-房间图中的变量,用带_meal的表示客人-菜图中的变量,用Match表示房间或菜当前匹配的客人,用Modefy标记客人-房间图中在匈牙利算法进行的时候修改的Match,用Las记录被修改前的值。那么我们就只需要在Hungary_meal匹配失败后用一个for循环把修改前的值改回来就可以啦。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std; const int maxN=200;
const int inf=2147483647; int n,P,Q;//p是房间,Q是菜
vector<int> Room[maxN];//图
vector<int> Meal[maxN];
bool Modefy[maxN];//因为有两个二分图,第二个不匹配时要把第一个中修改的改回来
int Last[maxN];
bool vis[maxN];//注意这里为什么不能用vis代替Modefy,因为vis在两个Hungary函数中都用到了,而Modefy要保留第一个Hungary的值直到判断出第二个是否匹配,所以不能用vis代替
int Match_room[maxN];
int Match_meal[maxN]; bool Hungary_room(int u);//房间的匈牙利
bool Hungary_meal(int u);//菜的匈牙利 int main()
{
cin>>n>>P>>Q;
for (int i=1;i<=n;i++)
for (int j=1;j<=P;j++)
{
int k;
scanf("%d",&k);
if (k==1)
Room[i].push_back(j);
} for (int i=1;i<=n;i++)
for (int j=1;j<=Q;j++)
{
int k;
scanf("%d",&k);
if (k==1)
Meal[i].push_back(j);
}
int Ans=0;
memset(Match_room,-1,sizeof(Match_room));
memset(Match_meal,-1,sizeof(Match_meal));
for (int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
memset(Modefy,0,sizeof(Modefy));
if (Hungary_room(i))
{
memset(vis,0,sizeof(vis));
if (Hungary_meal(i))
{
Ans++;
}
else
{
for (int i=1;i<=P;i++)//若菜匹配失败,则要把房间的改回来
if (Modefy[i]==1)
Match_room[i]=Last[i];
}
}
}
cout<<Ans<<endl;
} bool Hungary_room(int u)
{
for (int i=0;i<Room[u].size();i++)
{
int v=Room[u][i];
if (vis[v]==0)
{
vis[v]=1;
if ((Match_room[v]==-1)||(Hungary_room(Match_room[v])))
{
Modefy[v]=1;//记录下被改变的值的信息
Last[v]=Match_room[v];
Match_room[v]=u;
return 1;
}
}
}
return 0;
} bool Hungary_meal(int u)
{
for (int i=0;i<Meal[u].size();i++)
{
int v=Meal[u][i];
if (vis[v]==0)
{
vis[v]=1;
if ((Match_meal[v]==-1)||(Hungary_meal(Match_meal[v])))
{
Match_meal[v]=u;
return 1;
}
}
}
return 0;
}