更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19617614

大意

每一个小朋友在得到自己喜欢的饮料和食物的时候，就实现了其愿望，问最多能实现多少奶牛的愿望。

思路

首先我们考虑这样的三元关系 $(饮料，小朋友，食物)$，这样的三元关系，如果我们直接在中间连边去跑最大流是否有问题呢？

显然是有问题的，如下图：

这样我们发现个奇怪的问题，一个小朋友对应的喜欢的食物和饮料其实是很多的，但是这样会使得不同的饮料与食物都对一个小朋友产生影响，现在我们需要做的是给一个点上约束，而这种技巧叫做拆点。

我们考虑将每个小朋友拆为 $in$ 和 $out$，在 $in$ 和 $out$ 间连容量为 $1$ 的边，这样我们就可以保证每个小朋友只被算一次，如下图：

在拆完点之后直接跑最大流即可。

代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N = 1000;
const int MAX_M = 100000;
struct edge {
    int v, c, next;
} e[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int c) {
    e[eid].v = v;
    e[eid].next = p[u];
    e[eid].c = c;
    p[u] = eid++;
}
void addedge(int u, int v, int c) {
    insert(u, v, c);
    insert(v, u, 0);
}
int S, T;
int d[MAX_N];
bool bfs() {
    memset(d, -1, sizeof(d));
    queue<int> q;
    q.push(S);
    d[S] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = p[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (e[i].c > 0 && d[v] == -1) {
                q.push(v);
                d[v] = d[u] + 1;
            }
        }
    }
    return (d[T] != -1);
}
int dfs(int u, int flow) {
    if (u == T) {
        return flow;
    }
    int res = 0;
    for (int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (e[i].c > 0 && d[u] + 1 == d[v]) {
            int tmp = dfs(v, min(flow, e[i].c));
            flow -= tmp;
            e[i].c -= tmp;
            res += tmp;
            e[i ^ 1].c += tmp;
            if (flow == 0) {
                break;
            }
        }
    }
    if (res == 0) {
        d[u] = -1;
    }
    return res;
}
int Dinic() {
    int res = 0;
    while (bfs()) {
        res += dfs(S, INF);
    }
    return res;
}
int main() {
    init();
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i ++){
        addedge(m + i, m + n + i, 1);
        int a, b; cin >> a >> b;
        for(int j = 0;j < a;j ++){
            int x; cin >> x;
            addedge(x, m + i, 1);
        }
        for(int j = 0;j < b;j ++){
            int x; cin >> x;
            addedge(m + n + i, m + 2 * n + x, 1);
        }
    }
    S = 0; T = m + 2 * n + k + 1;
    for(int i = 1;i <= m;i ++){
        addedge(S, i, 1);
    }
    for(int i = 1;i <= k;i ++){
        addedge(m + 2 * n + i, T, 1);
    }
    cout << Dinic() << endl;
    return 0;
}

考虑网络流求解这类分配问题。

建立源点 $S$，汇点 $T$。令从 $S$ 到 $T$ 的一条路径表示一个奶牛得到了喜欢的食物和饮料。

显然需要对每个食物 $i$ 建立点 $f_i$，对饮料 $j$ 建立点 $d_j$。

食物的点集和饮料的点集显然不能同时连向源点 $S$，不妨对于每个 $f_i,d_j$ 建立 $S \to f_i$ 和 $d_j \to T$ 的容量为 $1$ 的有向边。

如果每个奶牛直接和食物和饮料的集合连边，那么很可能会出现同一个奶牛同时享有多种食物和饮料的情况，然而这时奶牛对最大流的贡献仅为 $1$，求出的最大流却有可能很大。

考虑对其进行限制。对于每个奶牛，建立两个点，两点间连一条容量为 $1$ 的边，这两个点再分别与喜欢的食物和饮料相连，这样就能保证同一个奶牛至多满足一次。

最后直接在建出的图上跑最大流即可。

（代码很丑，见谅）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 20005;
int ver[maxn << 1],nxt[maxn << 1],cap[maxn << 1],head[maxn];
int cnt = -1;
int cur[maxn],level[maxn];
queue <int> q; 
void add(int u,int v,int t) {
    nxt[++ cnt] = head[u];
    ver[cnt] = v;
    cap[cnt] = t;
    head[u] = cnt;
    return ;
}
void AddEdge(int u,int v) {
    add(u , v , 1);
    add(v , u , 0);
    return ;
}
int n;
bool bfs(int s,int t) {
    memset(level , 0 , sizeof(level));
    q.push(s);
    level[s] = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u];~ i;i = nxt[i]) {
            int v = ver[i];
            if(!level[v]&&cap[i]) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] != 0;
}
int dfs(int x,int t,int maxflow) {
    if(x == t||!maxflow)return maxflow;
    int flow = 0,f;
    for(int& i = cur[x];~ i;i = nxt[i]) {
        int v = ver[i];
        if(level[v] == level[x] + 1&&(f = dfs(v , t , min(maxflow , cap[i])))) {
            if(!f) {
                level[v] = 0;
                break ;
            }
            flow += f;
            maxflow -= f;
            cap[i] -= f;
            cap[i ^ 1] += f;
            if(!maxflow)break;
        }
    }
    return flow;
}
int Dinic(int s,int t) {
    int flow = 0;
    while(bfs(s , t)) {
        memcpy(cur , head , sizeof(cur));
        flow += dfs(s , t , 0x3f3f3f3f);
    }
    return flow;
}
int S,T,tot,f[maxn],d[maxn],F,D,c1[maxn],c2[maxn];
int main() {
    freopen("usaco_open07_dining.in","r",stdin);
    freopen("usaco_open07_dining.out","w",stdout);
    scanf("%d%d%d",&n,&F,&D);
    memset(head , -1 , sizeof(head));
    S = ++ tot;
    T = ++ tot;
    for(int i = 1;i <= F;++ i)f[i] = ++ tot,AddEdge(S , f[i]);
    for(int i = 1;i <= D;++ i)d[i] = ++ tot,AddEdge(d[i] , T);
    for(int i = 1;i <= n;++ i)c1[i] = ++ tot,c2[i] = ++ tot,AddEdge(c1[i] , c2[i]);
    for(int i = 1;i <= n;++ i) {
        int x,y,z;
        scanf("%d%d",&x,&y);
        for(int j = 1;j <= x;++ j) {
            scanf("%d",&z);
            AddEdge(f[z] , c1[i]);
        }
        for(int j = 1;j <= y;++ j) {
            scanf("%d",&z);
            AddEdge(c2[i] , d[z]);
        }
    }
    printf("%d\n",Dinic(S , T));
    fclose(stdin);
    fclose(stdout);
    return 0;
}

建图：源点->食物->牛->牛->饮料->汇点

边权都是1

跑最大流

然后就A了