洛谷P1402 酒店之王(二分图)

P1402 酒店之王

题目描述

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<cstring>

#define N 101

using 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=; i<=n; i++)

        if (RL[No][i]&&!visR[i])

        {

            visR[i]=;

            if (book[i]==||room_(book[i]))

            {

                CR[No]=;

                book[i]=No;

                return ;

            }

        }

    return ;

}

bool food_(int No)

{

    for (int i=; i<=n; i++)

        if (FL[No][i]&&!visF[i])

        {

            visF[i]=;

            if (eat[i]==||food_(eat[i]))

            {

                CF[No]=;

                eat[i]=No;

                return ;

            }

        }

    return ;

}

int main ()

{

    scanf("%d%d%d",&n,&p,&q);

    for (i=; i<=n; i++)

        for (j=; j<=p; j++)

            scanf("%d",&RL[i][j]);

    for (i=; i<=n; i++)

        for (j=; j<=q; j++)

            scanf("%d",&FL[i][j]);

    while ()

    {

        for (i=; i<=n; i++)

            if (!CR[i])

            {

                for (j=; j<=n; j++) visR[j]=;

                for (j=; j<=n; j++) visF[j]=;

                for (j=; j<=n; j++) LCR[j]=CR[j];

                for (j=; j<=n; j++) LB[j]=book[j];

                if (room_(i)&&food_(i))

                {

                    answer++;

                    continue;

                }

                else//因为无法匹配所以取消上次所有增广

                {

                    for (j=; j<=n; j++) CR[j]=LCR[j];

                    for (j=; j<=n; j++) book[j]=LB[j];

                }

            }

        break;

    }

    printf("%d\n",answer);

    return ;

    return ;

    return ;

}