幼儿园开学啦！ 在开学前，有的小朋友会准备一个毛绒玩具，可以分享给其他小朋友~ 具体的，一共有 � t 天，每天的座位表可以表示成一张无向图。每天有毛绒玩具的小朋友一定会选择一个在这一天和他坐在一起的小朋友，并把毛绒玩具送给他。 但是老师规定，每个人只能有一个毛绒玩具。 在这里，我们认为每天每个人会先送出玩具，再从别人那里接受。 问初始时最多可以有多少小朋友有毛绒玩具。 注意：这意味着一个合法的传递过程中不能如果出现存在小朋友送不出毛绒玩具或者存在小朋友拥有超过一个毛绒玩具的情况，一个初始局面是合法的当且仅当存在一种合法的传递过程。 输入格式 第一行两个正整数 � , � t,n。 后描述 � t 张图，表示每天的座位表： 每个描述的第一行是一个正整数 � m 表示边数。 后 � m 行每行两个正整数 � , � u,v 表示图中存在一条无向边 ( � , � ) (u,v)。请写出具体的代码

以下是基于网络流的具体实现：

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 210, M = 40010;

struct Edge
{
    int v, w, nxt;
} e[M];

int h[N], idx;
int cur[N], d[N];
int n, m, S, T;

void add(int u, int v, int w)
{
    e[idx].v = v, e[idx].w = w, e[idx].nxt = h[u], h[u] = idx++;
    e[idx].v = u, e[idx].w = 0, e[idx].nxt = h[v], h[v] = idx++;
}

bool bfs()
{
    memset(d, -1, sizeof d);
    queue<int> q;
    q.push(S);
    d[S] = 0;
    cur[S] = h[S];
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = h[u]; i != -1; i = e[i].nxt)
        {
            int v = e[i].v, w = e[i].w;
            if (d[v] == -1 && w)
            {
                d[v] = d[u] + 1;
                cur[v] = h[v];
                if (v == T)
                    return true;
                q.push(v);
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T)
        return limit;
    int flow = 0;
    for (int i = cur[u]; i != -1 && flow < limit; i = e[i].nxt)
    {
        cur[u] = i;
        int v = e[i].v, w = e[i].w;
        if (d[v] == d[u] + 1 && w)
        {
            int t = find(v, min(w, limit - flow));
            if (!t)
                d[v] = -1;
            e[i].w -= t;
            e[i ^ 1].w += t;
            flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while (bfs())
        while (flow = find(S, 1e9))
            res += flow;
    return res;
}

int main()
{
    cin >> n >> m;
    S = 0, T = n + m + 1;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++)
    {
        int k;
        cin >> k;
        while (k--)
        {
            int u;
            cin >> u;
            add(u, i + n, 1);
        }
        add(S, i + n, 1);
    }
    for (int i = 1; i <= n; i++)
        add(i, T, 1);
    cout << dinic() << endl;
    return 0;
}

注意，为了保证一个小朋友不会送出或接收多个毛绒玩具，我们在建图时需要将每个小朋友拆成两个点，即一个表示送出毛绒玩具，一个表示接收毛绒玩具。