洛谷P1402 酒店之王题解

题意：

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

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

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

输入格式：

第一行给出三个整数，分别表示表示 $n,p,q$。

之后 $n$ 行，每行 $p$ 个整数，只可能是 $0$ 或 $1$，第 $i$ 行第 $j$ 个数表示第 $i$ 个人喜不喜欢第 $j$ 个房间（$1$ 表示喜欢， $0$ 表示不喜欢）。

之后 $n$ 行，每行 $q$ 个整数，只可能是 $0$ 或 $1$，第 $i$ 行第 $j$ 个数表示第 $i$ 个人喜不喜欢第 $j$ 道菜（$1$ 表示喜欢， $0$ 表示不喜欢）。

输出格式：

最大的顾客满意数。

数据范围：

对于全部的测试点，保证 $1 \leq n,p,q \leq 100$。

网络流经典题。

我们可以将所有人和所有菜连边，这构成了一个二分图。

然后我们再将所有人和所有房间连边，这构成了一个“镜像的二分图”

但是因为一个人只能匹配一个酒店&一道菜，这意味着需要把人拆点。

具体地，点 $A$ 拆成点 $A$ 和 $A’$ ，有边 $A \to A’$ 流量为 $1$ （以及反向边流量为 $0$ ）

然后只要把左侧的酒店和源点 $s$ 连一下，右侧的菜和 $t$ 连一下，跑个最大流就好了。

时间复杂度 $\mathcal{O}(|V|^2|E|)$ ，采用了 $\mathtt{Dinic}$ （~~其实是怕记错 ISAP 然后调半天~~）

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(155))
#define M ((int)(1e6 + 255))

// A : [1,n], B : [n+1,n+p];
// C : [n+p+1, n+p+q], A' : [n+p+q+1, n+p+q+n];
int n,p,q,s,t,tot,pos=1,head[N * 4],dep[N * 4],now[N * 4];
struct Edge { int u,v,w,next; } e[M * 4];
void addEdge(int u,int v,int w)
{ e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
void add(int u,int v) { addEdge(u,v,1); addEdge(v,u,0); }
queue<int> que;
bool bfs()
{
    for(int i=1; i<=tot; i++) dep[i] = INF;
    que.push(s); dep[s] = 0; now[s] = head[s];
    while(!que.empty())
    {
        int u = que.front(); que.pop();
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v;
            if(e[i].w > 0 && dep[v] == INF)
            {
                dep[v] = dep[u] + 1;
                now[v] = head[v]; que.push(v);
            }
        }
    }
    return dep[t] != INF;
}
int dfs(int u,int in)
{
    if(u == t) return in;
    int out = 0;
    for(int i=now[u]; i; i=e[i].next)
    {
        if(!in) break; int v = e[i].v; now[u] = i;
        if(e[i].w > 0 && dep[v] == dep[u] + 1)
        {
            int res = dfs(v, min(in, e[i].w));
            e[i].w -= res; e[i ^ 1].w += res;
            in -= res; out += res;
        }
    }
    if(!out) dep[u] = INF;
    return out;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> p >> q; tot = n + p + q + n; s = ++tot; t = ++tot;
    for(int i=1; i<=n; i++)
        for(int j=1,x; j<=p; j++) { cin >> x; if(x) add(j+n, i); }
    for(int i=1; i<=n; i++)
        for(int j=1,x; j<=q; j++) { cin >> x; if(x) add(i+p+q+n, j+n+p); }
    
    for(int i=1; i<=p; i++) add(s, i+n);
    for(int i=1; i<=q; i++) add(i+n+p, t);
    for(int i=1; i<=n; i++) add(i, i+n+p+q);
    int maxflow = 0;
    while(bfs()) maxflow += dfs(s, INF);
    cout << maxflow << '\n';
    return 0;
}