Luogu2891 吃饭

网络流

Luogu

我们考虑将牛拆成两个点，来限制其享用食物或饮料的种类数（每头牛只能享用一种食物和饮料），然后对于每头牛喜爱的列表连边，再建立超级源，超级汇，最后跑一遍最大流就行啦。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
const int INF = 0x3f3f3f3f;
const int MAXN = 100;
const int MAXM = MAXN * MAXN * 2 + MAXN * 3;
int n, m, k, sp, ep, edge = -1;
int firstEdge[MAXN * 4 + 2], curEdge[MAXN * 4 + 2], depth[MAXN * 4 + 2];
struct Edge {
    int to, f, nxt;
    Edge(){}
    Edge(int x, int y, int z) {
        to = y;
        f = z;
        nxt = firstEdge[x];
    }
} e[MAXM << 1 | 1];
inline int read() {
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
inline void addEdge(int x, int y, int z) {
    e[++edge] = Edge(x, y, z);
    firstEdge[x] = edge;
}
bool getDepth() {
    std::queue <int> q;
    memset(depth, 0, sizeof(depth));
    depth[sp] = 1;
    q.push(sp);
    do {
        int from = q.front();
        q.pop();
        for(int k = firstEdge[from]; ~k; k = e[k].nxt) {
            int to = e[k].to, f = e[k].f;
            if(f > 0 && !depth[to]) {
                depth[to] = depth[from] + 1;
                q.push(to);
            }
        }
    } while(!q.empty());
    return depth[ep] > 0;
}
int Augment(int x, int flow) {
    if(x == ep) return flow;
    for(int &k = curEdge[x]; ~k; k = e[k].nxt) {
        int to = e[k].to, f = e[k].f;
        if(f > 0 && depth[to] == depth[x] + 1) {
            int tmp = Augment(to, std::min(flow, f));
            if(tmp > 0) {
                e[k].f -= tmp;
                e[k ^ 1].f += tmp;
                return tmp;
            }
        }
    }
    return 0;
}
int Dinic() {
    int res = 0, tmp;
    while(getDepth()) {
        for(int i = sp; i <= ep; ++i) curEdge[i] = firstEdge[i];
        while((tmp = Augment(sp, INF)) > 0) res += tmp;
    }
    return res;
}
int main() {
    n = read();
    m = read();
    k = read();
    sp = 0;
    ep = 2 * n + m + k + 1;
    memset(firstEdge, -1, sizeof(firstEdge));
    for(int i = 1; i <= n; ++i) {
        int tmp1 = read(), tmp2 = read(), tmp3;
        while(tmp1--) {
            tmp3 = read();
            addEdge(2 * n + tmp3, i, 1);
            addEdge(i, 2 * n + tmp3, 0);
        }
        addEdge(i, i + n, 1);
        addEdge(i + n, i, 0);
        while(tmp2--) {
            tmp3 = read();
            addEdge(i + n, tmp3 + 2 * n + m, 1);
            addEdge(tmp3 + 2 * n + m, i + n, 0);
        }
    }
    for(int i = 1; i <= m; ++i) {
        addEdge(sp, i + 2 * n, 1);
        addEdge(i + 2 * n, sp, 0);
    }
    for(int i = 1; i <= k; ++i) {
        addEdge(2 * n + m + i, ep, 1);
        addEdge(ep, 2 * n + m + i, 0);
    }
    printf("%d\n", Dinic());
    return 0;
}