P1402 酒店之王题解

SunnyYuan的博客 / 2024-07-15 / 原文

考虑使用网络流。

分为 $6$ 层。

第一层为源点。

第二层为所有菜的点。

第三层和第四层都表示人。（限制只能选择一个）。

第五层为房子。

第六层为汇点。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 410, M = 101000, INF = 0x3f3f3f3f3f3f3f3f;

int n, m, S, T;

struct edge {
    int to, next, w;
} e[M];

int head[N], idx = 1;

void add(int u, int v, int w) {
    // cout << u << ' ' << v << ' ' << w << endl;
    idx++, e[idx].to = v, e[idx].next = head[u], e[idx].w = w, head[u] = idx;
    idx++, e[idx].to = u, e[idx].next = head[v], e[idx].w = 0, head[v] = idx;
}

int dep[N];

bool bfs() {
    queue<int> q;
    q.push(S);
    memset(dep, 0x3f, sizeof(dep));
    dep[S] = 1;

    while (q.size()) {
        int t = q.front();
        q.pop();

        for (int i = head[t]; i; i = e[i].next) {
            int to = e[i].to;
            if (dep[to] > dep[t] + 1 && e[i].w) {
                dep[to] = dep[t] + 1;
                q.push(to);
            }
        }
    }
    return dep[T] < INF;
}

int dinic(int u, int limit) {
    if (u == T) return limit;
    int rest = limit;
    for (int i = head[u]; i && rest; i = e[i].next) {
        int to = e[i].to;
        if (dep[to] == dep[u] + 1 && e[i].w) {
            int k = dinic(to, min(rest, e[i].w));
            if (!k) dep[to] = INF;
            rest -= k;
            e[i].w -= k;
            e[i ^ 1].w += k;
        }
    }
    return limit - rest;
}

int p, q;

signed main() {
    // freopen("a.in", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    S = 0, T = N - 1;
    cin >> n >> p >> q;
  
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= p; j++) {
            int x;
            cin >> x;
            if (x) add(j, i + 100, 1);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= q; j++) {
            int x;
            cin >> x;
            if (x) add(i + 200, j + 300, 1);
        }
    }

    for (int i = 1; i <= 100; i++) add(i + 100, i + 200, 1);
 
    for (int i = 1; i <= 100; i++) add(S, i, 1);
    for (int i = 301; i <= 400; i++) add(i, T, 1);

    int maxflow = 0, flow = 0;
    while (bfs()) while (flow = dinic(S, INF)) maxflow += flow;
    cout << maxflow << '\n';
    return 0;
}