幼儿园开学啦! 在开学前,有的小朋友会准备一个毛绒玩具,可以分享给其他小朋友~ 具体的,一共有 � t 天,每天的座位表可以表示成一张无向图。每天有毛绒玩具的小朋友一定会选择一个在这一天和他坐在一起的小朋友,并把毛绒玩具送给他。 但是老师规定,每个人只能有一个毛绒玩具。 在这里,我们认为每天每个人会先送出玩具,再从别人那里接受。 问初始时最多可以有多少小朋友有毛绒玩具。 注意:这意味着一个合法的传递过程中不能如果出现存在小朋友送不出毛绒玩具或者存在小朋友拥有超过一个毛绒玩具的情况,一个初始局面是合法的当且仅当存在一种合法的传递过程。 输入格式 第一行两个正整数 � , � t,n。 后描述 � t 张图,表示每天的座位表: 每个描述的第一行是一个正整数 � m 表示边数。 后 � m 行每行两个正整数 � , � u,v 表示图中存在一条无向边 ( � , � ) (u,v)。请写出c++代码
时间: 2024-04-02 07:31:26 浏览: 56
题目描述
幼儿园开学啦! 在开学前,有的小朋友会准备一个毛绒玩具,可以分享给其他小朋友~ 具体的,一共有t天,每天的座位表可以表示成一张无向图。每天有毛绒玩具的小朋友一定会选择一个在这一天和他坐在一起的小朋友,并把毛绒玩具送给他。 但是老师规定,每个人只能有一个毛绒玩具。 在这里,我们认为每天每个人会先送出玩具,再从别人那里接受。 问初始时最多可以有多少小朋友有毛绒玩具。 注意:这意味着一个合法的传递过程中不能如果出现存在小朋友送不出毛绒玩具或者存在小朋友拥有超过一个毛绒玩具的情况,一个初始局面是合法的当且仅当存在一种合法的传递过程。
输入格式
第一行两个正整数t,n。
后描述t张图,表示每天的座位表:
每个描述的第一行是一个正整数m表示边数。
后m行每行两个正整数u,v表示图中存在一条无向边(u,v)。
输出格式
一个整数,表示初始时最多可以有多少小朋友有毛绒玩具。
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` 数组表示每个座位匹配的小朋友编号。
怎么能不让小猫咪在家跑酷
1. 提供足够的活动空间:给小猫咪提供一个宽敞的活动空间,让它们能够自由地奔跑和玩耍。
2. 提供足够的玩具:给小猫咪提供丰富的玩具,包括球、毛绒玩具、猫抓板等,让它们能够在家里找到乐趣。
3. 定期遛猫:如果条件允许,可以定期带小猫咪出门遛弯,让它们能够在户外活动和玩耍。
4. 约束活动范围:在家中设置猫栏或者限制小猫咪的活动范围,防止它们跑到危险的地方。
5. 给予足够的关注:给小猫咪足够的关注和陪伴,让它们感到安全和满足,减少其想要在家里奔跑的欲望。