当前位置: 首页 > news >正文

【每日一题】【二分图最大匹配】【经典板子题】有大家喜欢的零食吗 河南萌新联赛2024第(一)场:河南农业大学 C题 C++

河南萌新联赛2024第(一)场:河南农业大学 C题

有大家喜欢的零食吗

题目描述

在某幼儿园中共有 n n n个小朋友,该幼儿园的老师为这 n n n 个小朋友准备了 n n n 份不一样的零食大礼包。每个小朋友只能选择一个,但老师并不知道小朋友们喜欢什么类型的零食大礼包,因此,老师让小朋友们分别说出了他们喜欢的零食大礼包都有哪些,老师希望能根据小朋友们的叙述来让所有的小朋友们都能吃到他们喜欢的零食。若并非所有的小朋友都能吃到自己满意的零食,请问老师最少还应购买多少份零食大礼包来保证所有的小朋友都能吃到自己满意的零食。

题目保证任意一个小朋友都会喜欢这 n n n 种大礼包中的至少一种。

在这里插入图片描述

样例 #1

样例输入 #1

3
2 1 2
1 3
3 1 2 3

样例输出 #1

Yes

说明

根据题目描述和样例,老师可以选择给第一个小朋友1号大礼包,给第二个小朋友3号大礼包,给第三个小朋友2号大礼包。这样可以保证每个小朋友可以吃到自己喜欢的零食

样例 #2

样例输入 #2

3
2 1 2
1 1
2 1 2

样例输出 #2

No
1

做题思路

首先这道题是很典型的二分图最大匹配题
如果不懂二分图最大匹配题如何做可以看文章
【每日一题】【二分图最大匹配】【匈牙利算法】【增广路径】 P3386 【模板】二分图最大匹配 C++

在某幼儿园中共 n n n个小朋友,该幼儿园的老师为这 n 个小朋友准备了 n n n份不一样的零食大礼包每个小朋友只能选择一个

然后问能不能所有小朋友都吃到喜欢吃的。

n n n个小朋友看为一个集合,把 n n n份不一样的零食大礼包看为另一个集合,一个小朋友只能选一个,也就说两个集合间的元素连线。
这就是典型的二分图

需要最多的小朋友迟到喜欢吃的,也就是说尽量多的小朋友能选择到。
这就是典型的二分图最大匹配问题(小朋友匹配零食)

具体修改板子的地方

只需要读取的时候改一下,就可以用了

cin >> n;int k;for(int i=1;i<=n;i++){cin >> k;for(int j=1;j<=k;j++){cin >> v;eg[i].push_back(v);//第i个小孩喜欢v零食,有这条边}}

时间复杂度 + 伪代码

因为至少改模板的输入,其他不变所以,时间复杂度分析+伪代码具体可以参考模板的文章。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace  std;
const int N = 5e4+10;
int n,m,e , u , v , cnt;
int mach[N],vis[N];
vector<int>eg[N];
bool dfs(int x,int flag){for(auto i:eg[x]){if(vis[i])continue;vis[i] = true;if(!mach[i] || dfs(mach[i],flag)){//没有被匹配 或 有增广路径mach[i] = x; // 右边的 i 点匹配上左边的 x 点return true;}}return false;
}
int main(){cin >> n;int k;for(int i=1;i<=n;i++){cin >> k;for(int j=1;j<=k;j++){cin >> v;eg[i].push_back(v);}}for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(dfs(i,i)){cnt++;}}if(cnt == n)cout << "Yes";else cout << "No\n" << n - cnt;return 0;
}
http://www.lryc.cn/news/416113.html

相关文章:

  • 【python】OpenCV—Image Colorization
  • vue 学习笔记
  • 武汉流星汇聚:‘中国制造’闪耀欧洲站,体育赛事成亚马逊增长点
  • RPA是什么?探讨RPA发展的最新趋势 | RPA研究
  • sqlalchemy时间范围查询
  • 电脑不小心删除的文件怎么恢复?教你文件恢复的绝招
  • stm32:使用和学习--硬件和程序
  • ARM知识点二
  • C# ?的使用
  • 【unity小技巧】unity性能优化以及如何进行性能测试
  • 算法参考改进点/知识点
  • electron 配置、打包 -报错解决
  • 基于STM32设计的智能鱼缸(华为云IOT)(200)
  • Django与数据库
  • 大数据系列之:CentOS7安装R详细步骤
  • Linux学习第57天:Linux PWM驱动实验
  • git 远程拉取指定文件
  • 【css】 CSS3+JS做一个酷炫的仪表进度条3d进度条
  • uniapp小程序全局配置分享到朋友和朋友圈功能的实现
  • Java优化后台分页
  • <数据集>电梯内人车识别数据集<目标检测>
  • 二百五十三、OceanBase——Linux上安装OceanBase数据库(三):OBD页面上部署OceanBase数据库
  • Redis应用笔记
  • html实现好看的塔罗牌、十二星座运势网站源码
  • 万字长文带你入门shell编程(超详细)
  • 音质提升秘籍:专业音频剪辑软件汇总
  • idea配置
  • 将 WinForms 中的 Panel 替换为 WPF 的 WindowsFormsHost 元素
  • C++ ---- vector的底层原理剖析及其实现
  • 跑酷视频素材去哪里下载?哪里有跑酷游戏视频素材?