餐饮问题

解题思路

本题是要求每头牛、每瓶饮料、每个食物只能用一次，且每组配对包含一头牛和它喜好的饮料、食物，要求最大匹配数。

可以发现本题很像二分图匹配，但是本题有三个种类，因此说是三分图匹配更合适。

而这么看来，一种显然的建图方式就是用类似二分图匹配的方法来建图，即从每个食物向喜欢它的牛连一条容量为 $1$ 的边，从每头牛向它喜欢的饮料连一条容量为 $1$ 的边。

以上方式建出来的图中的可行流能和原问题的可行解对应起来吗？答案是不行的，因为每头牛可能喜欢 $2$ 个及以上的饮料和食物，那么这时按照流量的角度来看，这两个饮料可以各自经过这同一头牛再分别经过两个食物到达汇点，导致一头牛产生 $2$ 个及以上的匹配，这与题意要求的每头牛只能用一次不符。

因此可以发现这样建图的问题在于牛的使用次数不好控制，但是饮料和食物的使用次数都被限制为 $1$ 次。这里可以用一个非常经典的拆点技巧，将每头牛拆成一个入点和一个出点，原先连向它的边变成连向入点的边，原先从它连出去的边变成从出点连出去的边。然后从入点向出点连一条容量为 $1$ 的边，保证再多的流量流向这头牛，在经过中间这条容量为 $1$ 的边之后，也只能走出来一组匹配，通过一个通道完美的限制了牛的使用次数。

注意：这里总结了一个网络流建图的重要技巧，如果对边有限制，直接对边的容量进行限制即可。如果对点有限制，可以将点拆成入点和出点，然后在入点和出点之间的通道上进行容量限制即可。

然后还需要证明原问题的可行解能否和流网络的可行流对应，由于流网络中已经保证了饮料、牛、食物都只能使用一次的限制，并且也根据牛的喜好进行连边，因此很好证明两者之间的对应关系，这里就不再赘述。

得证原问题的可行解和流网络的可行流一一对应后，原问题的最大匹配数就是流网络的最大可行流，因此最后再求一次最大流的流量就是答案。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 410, M = 40610, INF = 0x3f3f3f3f;

int n, m1, m2, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往汇点能传输的最大流量，传输上限为 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //dinic 求最大流
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d%d%d", &n, &m1, &m2);

    memset(h, -1, sizeof h);

    //牛的入点编号 1~n，牛的出点编号 n+1~2*n，食物编号 2*n+1~2*n+m1，饮料编号 2*n+m1+1~2*n+m1+m2
    S = 0, T = n * 2 + m1 + m2 + 1;
    for(int i = 1; i <= m1; i++) add(S, 2 * n + i, 1); //从源点向每个食物连一条容量为 1 的边
    for(int i = 1; i <= m2; i++) add(2 * n + m1 + i, T, 1); //从每个饮料向汇点连一条容量为 1 的边
    for(int i = 1; i <= n; i++)
    {
        add(i, i + n, 1); //对于每头牛，从入点向出点连一条容量为 1 的边

        int a, b;
        scanf("%d%d", &a, &b);
        while(a--)
        {
            int x;
            scanf("%d", &x);
            add(n * 2 + x, i, 1); //从第 i 头牛喜爱的所有食物向第 i 头牛的入点连一条容量为 1 的边
        }
        while(b--)
        {
            int x;
            scanf("%d", &x);
            add(i + n, n * 2 + m1 + x, 1); //从第 i 头牛的出点向第 i 头牛喜爱的所有饮料连一条容量为 1 的边
        }
    }
    printf("%d\n", dinic());

    return 0;
}