建图

我们可以看看如何建图。首先保证每一份食物和饮品都只使用过一次。
饿哦们可以把食物建在牛的 左边,饮品建在牛的右边。
食物连源点,饮品连汇点。这样就满足了。

但是还有一个要注意的地方。就是每一头牛只能用一次。
也就是说,我们每一头牛只能用一次。所以,要对牛进行拆点。

代码如下:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<functional>
using namespace std;
const int inf = 2e9;
const int max_n = 500;
const int max_m = 21000;
struct edge{
    int to, cap, rev, next;
}E[max_m << 2];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cap,int rev) {
    E[cnt].to = to;E[cnt].cap = cap;
    E[cnt].next = head[from];E[cnt].rev = rev;
    head[from] = cnt++;
}

int d[max_n];
bool searchpath(int s,int t) {
    queue<int> que;que.push(s);
    fill(d, d + max_n, -1);d[s] = 0;
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (e.cap <= 0 || d[e.to] != -1)continue;
            d[e.to] = d[u] + 1;
            que.push(e.to);
        }
    }return d[t] != -1;
}
int iter[max_n];
int matchpath(int u,int t,int f) {
    if (u == t)return f;
    for (int& i = iter[u];i;i = E[i].next) {
        edge& e = E[i];
        if (e.cap <= 0 || d[e.to] <= d[u])continue;
        int flow = matchpath(e.to, t, min(e.cap, f));
        if (flow > 0) {
            e.cap -= flow;
            E[e.rev].cap += flow;
            return flow;
        }
    }return false;
}
int dinic(int s, int t) {
    int flow = 0;int f;
    while (searchpath(s, t)) {
        for (int i = 1;i < max_n;++i)iter[i] = head[i];
        while (f = matchpath(s, t, inf))
            flow += f;
    }return flow;
}

int N, F, D;
int main() {
    scanf("%d %d %d", &N, &F, &D);
    for (int i = 1, Fi, Di;i <= N;++i) {
        scanf("%d %d", &Fi, &Di);
        for (int j = 1, food;j <= Fi;++j) {
            scanf("%d", &food);
            add(food + 2 * N, i, 1, cnt + 1);
            add(i, food + 2 * N, 0, cnt - 1);
        }for (int j = 1, drink;j <= Di;++j) {
            scanf("%d", &drink);
            add(i + N, drink + 2 * N + F, 1, cnt + 1);
            add(drink + 2 * N + F, i + N, 0, cnt - 1);
        }
    }int start = 2 * N + F + D + 1;
    int ed = start + 1;
    for (int i = 1;i <= N;++i) {
        add(i, i + N, 1, cnt + 1);
        add(i + N, i, 0, cnt - 1);
    }for (int i = 1;i <= F;++i) {
        add(start, i + 2 * N, 1, cnt + 1);
        add(i + 2 * N, start, 0, cnt - 1);
    }for (int i = 1;i <= D;++i) {
        add(i + 2 * N + F, ed, 1, cnt + 1);
        add(ed, i + 2 * N + F, 0, cnt - 1);
    }printf("%d", dinic(start, ed));
}