P1402 酒店之王[网络瘤(正解)/匈牙利(错解)]

时间:2023-03-08 16:04:24
P1402 酒店之王[网络瘤(正解)/匈牙利(错解)]

题目描述

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

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

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

解析

学了匈牙利,还是讲一个匈牙利的做法。

先说一点,目前并没有找到匈牙利二分图匹配做法完全正确的例子。

分析一下思路问题。

最开始我的思路是直接匹配房和菜,交上去只有40分,仔细思考发现这样一个细节:如果直接匹配房菜,实际上可以把匹配边抽象成一个人,那么在匈牙利找出一条增广路时,会把之前配对的房菜弃用,通俗的讲就是这对房菜其中一个再也不会被这个人使用,然鹅我们并不具体知道是哪一个,而且对于把边抽象成人这个说法又不太准确,毕竟有可能边连的比人还多。而真实情况是,这个人既有可能换房,也有可能换菜,我们要分别考虑。能对4个点已经很不错了。

所以,我们需要建两个图,把人记下来当作未匹配点,分别对菜、人和人、房同步进行二分图匹配。同步即,此时进行增广的起始点为同一个人。这样依次对所有人进行增广,跑一遍匈牙利算法,就可得出最大匹配。

这样还是错的,我就很纳闷,仔细一想,发现问题还是出现在相似的地方。两边同步进行二分图匹配时,我们需要考虑更多。我们发现当一个人无法进行增广时,他有可能是在其中一张图上无法增广,有可能在两张图上都无法增广。显然如果其中一张图无法增广,另一张图如果你还增广,就相当于这个人只选了一个东西,或者菜或者房,那显然不符合题目要求。所以我们索性就不管这个人了,直接跳过这个人不增广他,继续往后面的人增广。

如果这么写的话,是可以A这道题的,但是依然有人hack掉了。

至于被hack的原因,补充一点个人想法:

注意到上面提到的跳过无法增广的人的思路,实际上细想还是存在问题。试想,是否存在一种情况,我们选择了这个本应被跳过的人,然后挤掉了之前的某个人,会使得整体更优?按道理来讲我觉得是存在的,也就是说这种做法是有后效性的,或许某种后面的决策会影响到之前的决策,并且还会使整体更优?那么如果这样讲,匈牙利是做不了这题的,匈牙利算法本身就无法胜任(毕竟哪也没写它可以同时处理两张有交叉的二分图)。

仅个人理解,如有错误,望dalao指正。

参考代码

这回就真的只是参考了,能AC,但是不一定完全正确。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#define N 501
using namespace std;
inline int read()
{
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int a[N][N],b[N][N],n,p,q,f1[N],f2[N],res1[N],res2[N];
vector<int> g1[N],g2[N];
bitset<N> v1,v2;
inline bool dfs1(int x)//正宗二分图匹配
{
for(register int i=0;i<g1[x].size();++i){
int y=g1[x][i];
if(v1[y]) continue;
v1[y]=1;
if(!f1[y]||dfs1(f1[y])){
f1[y]=x;
return 1;
}
}
return 0;
}
inline bool dfs2(int x)
{
for(register int i=0;i<g2[x].size();++i){
int y=g2[x][i];
if(v2[y]) continue;
v2[y]=1;
if(!f2[y]||dfs2(f2[y])){
f2[y]=x;
return 1;
}
}
return 0;
}
int main()
{
n=read(),p=read(),q=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=p;++j) scanf("%d",&a[i][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=q;++j) scanf("%d",&b[i][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=p;++j)
for(int k=1;k<=q;++k)
//建图,这边我建图稍微麻烦了点,但是比较好理解
if(a[i][j]) g1[i].push_back(j+n),g1[j+n].push_back(i);
else if(b[i][k]) g2[i].push_back(k+n),g2[k+n].push_back(i);
int ans=0;
for(int i=1;i<=n;++i){
v1.reset(),v2.reset();
memcpy(res1,f1,sizeof(f1));
memcpy(res2,f2,sizeof(f2));
if(dfs1(i)&&dfs2(i)) ans++;
else{
memcpy(f1,res1,sizeof(f1));//回溯过程
memcpy(f2,res2,sizeof(f2));
}
}
cout<<ans<<endl;
return 0;
}