Luogu_P1402 酒店之王

### 二分图

题目链接
明显二分图
但是怎么维护两个
其实可以在匈牙利之前保存下来当前的链接状态
假如没办法把菜和房间都匹配上就还原会当前状态
具体看代码吧

代码如下：

#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int maxn=200;
int n,p,q,lk1[maxn],lk2[maxn],l1[maxn],l2[maxn],ans=0;
bool vs1[maxn],vs2[maxn];
vector<int> di[maxn],ci[maxn];
bool fd1(int x){
    for(int i=0;i<di[x].size();i++){
        int y=di[x][i];
        if(!vs1[y]){
            vs1[y]=1;
            if(!lk1[y] || fd1(lk1[y])) {
                lk1[y]=x;return 1;
            }
        }
    }
    return 0;
}
bool fd2(int x){
    for(int i=0;i<ci[x].size();i++){
        int y=ci[x][i];
        if(!vs2[y]){
            vs2[y]=1;
            if(!lk2[y] || fd2(lk2[y])) {
                lk2[y]=x;return 1;
            }
        }
    }
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&p,&q);
    for(int i=1;i<=n;i++)
        for(int x,j=1;j<=p;j++){
            scanf("%d",&x);
            if(x) di[i].push_back(j);
        }
    for(int i=1;i<=n;i++)
        for(int x,j=1;j<=q;j++){
            scanf("%d",&x);
            if(x) ci[i].push_back(j);
        }
    for(int i=1;i<=n;i++){
        memset(vs1,0,sizeof(vs1));memset(vs2,0,sizeof(vs2));
        for(int j=1;j<=p;j++) l1[j]=lk1[j];
        for(int j=1;j<=q;j++) l2[j]=lk2[j];
        if(fd1(i)&&fd2(i))
            ans++;
        else{
            for(int j=1;j<=p;j++) lk1[j]=l1[j];
            for(int j=1;j<=q;j++) lk2[j]=l2[j];
        }
    }
    printf("%d\n",ans);
    return 0;
}

Luogu_P1402 酒店之王 二分图

原文：https://www.cnblogs.com/ChrisKKK/p/11662470.html