lg1402

发表于 | 分类于 ， ， | 阅读数 次

链接:lg1402

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

    题解

  • 做两个最大匹配，如果都匹配上了，答案+1，否则返回上次状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
#define abs(x) x=x>0?x:(-x)
using namespace std;
const int N=300;
int l[N][N][2],m[N][2],vis[N][2],n,p,q,tp[N][2];
template <typename T>inline void read(T &x){
    char c;int sign=1;x=0;
    do{c=getchar(); if(c=='-')sign=-1;}while(c<'0'||c>'9');
    do{x=x*10+c-'0'; c=getchar();}while(c>='0'&&c<='9');
    x*=sign;
}

int find(int x,int op){
    rep(i,1,n)if(l[x][i][op]&&!vis[i][op]){
        vis[i][op]=1;
        if(!m[i][op]||find(m[i][op],op)){
            m[i][op]=x;
            return 1;
        }
    }
    return 0;
}

int main(){
    int ans=0;
    read(n);read(p);read(q);
    rep(i,1,n)rep(j,1,p)read(l[i][j][0]);
    rep(i,1,n)rep(j,1,q)read(l[i][j][1]);
    rep(i,1,n){
        rep(j,0,1)rep(k,1,n)tp[k][j]=m[k][j];
        memset(vis,0,sizeof(vis));
        if(find(i,0)&&find(i,1))ans++;
        else rep(j,0,1)rep(k,1,n)m[k][j]=tp[k][j];
    }
    printf("%d\n",ans);
    return 0;
}