[Luogu 1402] 酒店之王

题目

Description

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

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

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

Input

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

之后n行，每行p个数包含0或1，第i个数表示喜不喜欢第i个房间（1表示喜欢，0表示不喜欢）。

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

Output

最大的顾客满意数。

Solution

第一眼看到就是网络流，但是怎么保证每个人不会被重复(分身)利用，每间房子和每道菜都只用一次呢？

拆点。

但是最开始的思路繁琐了很多，不是把人当做中间点，而是把菜和房间都当作中间点拆开，然后再把人拆开。。

这样的做法好sb，结果莫名 wa 了三个点，于是瞟了一眼题解，说把人当作中间点，这样只拆人即可。

恍然大悟，从超级源点向每道菜连流量为 1 的边，说明一道菜只能被用一次，同理，从每个房间向超级汇点连流量为 1 的边。然后把人拆点即可。

好题啊~

Code

// By YoungNeal
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int s,t,flow;
int a[1005];
int pre[1005];
int head[1005];
int n,p,q,cnt=1;

struct Edge{
    int to,nxt,flow;
}edge[1000005];

void add(int x,int y,int z){
    edge[++cnt].to=y;
    edge[cnt].nxt=head[x];
    edge[cnt].flow=z;
    head[x]=cnt;
}

bool bfs(){
    queue<int> q;
    memset(a,0,sizeof a);
    a[s]=0x3f3f3f3f;
    q.push(s);
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=edge[i].nxt){
            int to=edge[i].to;
            if(!edge[i].flow) continue;
            if(a[to]) continue;
            a[to]=min(a[u],edge[i].flow);
            pre[to]=i;
            q.push(to);
        }
    }
    if(!a[t]) return 0;
    flow+=a[t];
    return 1;
}

void update(){
    int m=t;
    for(;pre[m];m=edge[pre[m]^1].to)
        edge[pre[m]].flow-=a[t],edge[pre[m]^1].flow+=a[t];
}

signed main(){
    scanf("%d%d%d",&n,&p,&q);
    s=2*n+q+p+1,t=s+1;
    for(int i=1;i<=n;i++){
        for(int x,j=1;j<=p;j++){
            scanf("%d",&x);
            if(x^1) continue;
            add(j,p+i,1);
            add(p+i,j,0);
        }
    }
    for(int i=1;i<=n;i++){
        for(int x,j=1;j<=q;j++){
            scanf("%d",&x);
            if(x^1) continue;
            add(p+n+q+i,p+n+j,1);
            add(p+n+j,p+n+q+i,0);
        }
    }
    for(int i=1;i<=n;i++) add(p+i,p+n+q+i,1),add(p+n+q+i,p+i,0);
    for(int i=1;i<=p;i++) add(s,i,1),add(i,s,0);
    for(int i=p+1+n;i<=p+n+q;i++) add(i,t,1),add(t,i,0);
    while(bfs()) update();
    printf("%d",flow);
    return 0;
}

秒客网