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

这是一道经典的网络流问题，可以使用二分图匹配来解决。

对于每一天的座位表，我们可以将其中的小朋友看作二分图的左右两侧，每个小朋友都与他可以送出毛绒玩具的小朋友建立一条有向边，权值为1。然后，对这个二分图进行最大匹配，得到的匹配数即为这一天能够有多少小朋友得到毛绒玩具。

为了满足老师的规定，我们需要对每个小朋友送出毛绒玩具和接收毛绒玩具的过程进行建模。具体地，我们将每个小朋友拆成两个点，一个表示送出毛绒玩具，一个表示接收毛绒玩具，然后在这两个点之间连一条容量为1的边。

最后，我们将每一天的二分图全部合并起来，得到一个大的二分图，对其进行最大流计算，即可得到最多有多少小朋友能够得到毛绒玩具。

时间复杂度：$O(T \cdot (N+M)^2)$，其中 $T$ 是天数，$N$ 是小朋友的数量，$M$ 是座位表中的边数。

C++ 代码

相关问题

幼儿园开学啦！ 在开学前，有的小朋友会准备一个毛绒玩具，可以分享给其他小朋友~ 具体的，一共有 t 天，每天的座位表可以表示成一张无向图。每天有毛绒玩具的小朋友一定会选择一个在这一天和他坐在一起的小朋友，并把毛绒玩具送给他。 但是老师规定，每个人只能有一个毛绒玩具。 在这里，我们认为每天每个人会先送出玩具，再从别人那里接受。 问初始时最多可以有多少小朋友有毛绒玩具。c++代码

以下是使用 C++ 实现的代码，使用了邻接矩阵存储图：

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

using namespace std;

const int N = 105;

int n, m;
bool g[N][N];
bool vis[N];
int match[N];

bool dfs(int u) {
    for (int v = 1; v <= m; v++) {
        if (g[u][v] && !vis[v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int max_matching() {
    int res = 0;
    memset(match, -1, sizeof match);
    for (int u = 1; u <= n; u++) {
        memset(vis, false, sizeof vis);
        if (dfs(u)) res++;
    }
    return res;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        memset(g, false, sizeof g);
        for (int i = 1; i <= n; i++) {
            int cnt;
            cin >> cnt;
            while (cnt--) {
                int j;
                cin >> j;
                g[i][j] = true;
            }
        }
        cout << max_matching() << endl;
    }
    return 0;
}

该代码中，`g[u][v]` 表示第 `u` 个小朋友是否可以在第 `v` 天与另一个小朋友坐在一起，`vis` 数组表示在匈牙利算法中是否访问过节点，`match` 数组表示每个座位匹配的小朋友编号。