网络流板子题 + 拆点，你谷评分一如既往的虚高。

 

代码实现如下：

#include 
      
       using namespace std;#define rep(i, a, b) for (register int i = (a); i <= (b); i++)const int inf = 0x3f3f3f3f, maxn = 1e4 + 5;int n, f, d, S, T, tmp, ans = 0, f_sum, d_sum, num_edge = -1;int cur[maxn], dep[maxn], head[maxn];queue
       
         q;struct node {    int to, dis, nxt;}edge[maxn << 1];void origin(){memset(head, -1, sizeof(head));}int read() {    int x = 0, flag = 0;    char ch = ' ';    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();    if (ch == '-') {        flag = 1;        ch = getchar();    }    while (ch >= '0' && ch <= '9') {        x = (x << 1) + (x << 3) + ch - '0';        ch = getchar();    }    return flag ? -x : x;}void addedge(int from, int to, int dis) {    edge[++num_edge].nxt = head[from];    edge[num_edge].to = to;    edge[num_edge].dis = dis;    head[from] = num_edge;}int bfs(int S, int T) {    memset(dep, 0, sizeof(dep));    while (!q.empty()) q.pop();    memcpy(cur, head, sizeof(cur));    dep[S] = 1;    q.push(S);    while (!q.empty()) {        int u = q.front();        q.pop();        for (int i = head[u]; ~i; i = edge[i].nxt) {            int v = edge[i].to;            if (!dep[v] && edge[i].dis) {                dep[v] = dep[u] + 1;                q.push(v);            }        }    }    if (dep[T]) return 1;    return 0;}int dfs(int u, int flow) {    if (u == T || !flow) return flow;    int d, used = 0;    for (int i = cur[u]; ~i; i = edge[i].nxt) {        cur[u] = i;        int v = edge[i].to;        if (dep[v] == dep[u] + 1 && (d = dfs(v, min(flow, edge[i].dis)))) {            used += d;            flow -= d;            edge[i].dis -= d;            edge[i ^ 1].dis += d;            if (!flow) break;        }    }    if (!used) dep[u] = -2;    return used;}int dinic() {    int ans = 0;    while (bfs(S, T)) ans += dfs(S, inf);    return ans;}void write(int x) {    if (x < 0) {        putchar('-');        x = -x;    }    if (x > 9) write(x / 10);    putchar(x % 10 + '0');}int main() {    origin();    n = read(), f = read(), d = read();    S = 0, T = f + (n << 1) + d + 1;    rep(i, 1, f) {        addedge(S, i, 1);        addedge(i, S, 0);    }    rep(i, 1, n) {        addedge(f + i, f + n + i, 1);        addedge(f + n + i, f + i, 0);    }    rep(i, 1, d) {        addedge(f + (n << 1) + i, T, 1);        addedge(T, f + (n << 1) + i, 0);    }    rep(i, 1, n) {        f_sum = read(), d_sum = read();        rep(j, 1, f_sum) {            tmp = read();            addedge(tmp, f + i, 1);            addedge(f + i, tmp, 0);        }        rep(j, 1, d_sum) {            tmp = read();            addedge(f + n + i, f + (n << 1) + tmp, 1);            addedge(f + (n << 1) + tmp, f + n + i, 0);        }    }    ans = dinic();    write(ans);    return 0;}