【蓝桥杯集训·每日一题】AcWing1394. 完美牛棚
创始人
2024-06-01 10:24:23
0次

文章目录

  • 一、题目
    • 1、原题链接
    • 2、题目描述
  • 二、解题报告
    • 1、思路分析
    • 2、时间复杂度
    • 3、代码详解
  • 三、知识风暴
  • 匈牙利算法

一、题目

1、原题链接

1394. 完美牛棚

2、题目描述

农夫约翰上周刚刚建好了新的牛棚,并引进了最新的挤奶技术。

不幸的是,由于工程问题,牛棚中的每个单间都不太一样。

第一周,约翰将奶牛们随机分配在了各个单间中。

但是很快他就发现,每头奶牛都只愿意在一部分自己喜欢的单间中产奶。

在过去的一周中,农夫约翰一直在收集有关哪些奶牛愿意在哪些单间产奶的数据。

一个单间只能分配给一头奶牛,当然,一头奶牛也可能只愿意在一个单间中产奶。

给定奶牛的住宿喜好,请你计算,通过合理分配奶牛的住所,最多能够让多少奶牛可以住在自己愿意产奶的单间中。

输入格式

第一行包含两个整数 N 和 M,分别表示奶牛的数量以及单间的数量。

接下来 N 行,每行记录一个奶牛愿意产奶的单间信息。首先包含一个整数 Si,表示这头奶牛愿意在 Si 个单间中产奶。接下来包含 Si
个不同的整数,表示这些单间的编号。

所有单间的编号为 1∼M。

输出格式

输出一个整数,表示可以被分配在自己愿意产奶的单间中的奶牛的最大数量。

数据范围

0≤N,M≤200

0≤Si≤M

输入样例:

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

输出样例:

4

二、解题报告

1、思路分析

思路来源:y总讲解视频
y总yyds

(1)匈牙利算法模板题。
(2)直接套用模板即可。

2、时间复杂度

时间复杂度为O(n*m)

3、代码详解

#include 
#include 
using namespace std;
const int N=210,M=N*N;
int h[N],e[M],ne[M],idx;    //邻接表存储图
int n,m;
int match[N];    //存储和每头牛匹配的牛棚编号为多少
bool st[N];      //存储每个牛棚是否已经被遍历过
//邻接表加边
void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
//查找每头牛是否可以找到其心仪的牛棚和其匹配
bool find(int x){//枚举每头牛心仪的牛棚for(int i=h[x];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){     //如果当前牛棚未被遍历过st[j]=true;  //设置为已经遍历过if(match[j]==0||find(match[j])){    //如过当前牛棚没有和牛匹配或者已经匹配但是已经匹配的牛可以换一个牛棚,则直接将当前牛和该牛棚匹配match[j]=x;      //将当前牛和该牛棚匹配return true;     //匹配成功,返回true}}}return false;     //如果不存在和其匹配的牛棚返回false
}
int main(){cin>>n>>m;memset(h,-1,sizeof h);for(int i=1;i<=n;i++){int s;cin>>s;while(s--){int x;cin>>x;add(i,x);    //每次在每头牛和其心仪的牛棚之间添加一条有向边,由牛指向牛棚}}   int ans=0;//枚举每头牛,看其是否可以匹配成功for(int i=1;i<=n;i++){memset(st,false,sizeof st);     //枚举每头牛时,先将所有牛棚设置为未遍历过,因为该头牛要依次来查看其心仪的牛棚是否能够和自己匹配,而这些牛棚可能也是其他牛心仪的牛棚(可能在枚举其他牛的时候该牛棚已设置成已经遍历过),所以我们每次都应该将st[]清空if(find(i)) ans++;     //如果可以找到与其匹配的牛棚,答案+1}cout<

三、知识风暴

匈牙利算法

  • 匈牙利算法主要解决二分图的最大匹配问题。
  • 基本思想:枚举第一个集合中的点,每次都在第二个集合中查找是否存在可以与其匹配的点。
  1. 如果第一个集合中的点应该匹配的第二个集合中的点已经被匹配了,来看是否能够将已经匹配好的点拆散,让原匹配中的第一个集合中的点来找另一个可以与其匹配的第二个集合中的点,如果可以找到,那么原匹配被拆散,当前点与拆散后的第二集合中的点匹配,原匹配中的第一个集合中的点与新的第二个集合中的可以和其匹配的点匹配,否则,当前点无法完成匹配。
  2. 如果当前点应该匹配的第二个集合中的点正好没有被匹配,则他俩匹配即可。
  • 经过上述过程,来统计可以匹配的点的个数。

相关内容

热门资讯

内幕交易炒股避损7万被罚60万... 2026年11月12日,中国证监会北京监管局发布了一份针对有研硅(688432.SH)普通员工刘冰的...
普京:难怪您会选这里作为APE... 为期两天的亚太经合组织工商领导人峰会在深圳举行。俄罗斯总统普京在18日的峰会上发表致辞。普京表示,深...
猪价重回9元关口 养殖仍面临亏... 11月17日早上,28个重点监测地区瘦肉型标猪出栏均价为9.12元/公斤,比前一天上涨了一毛钱。尽管...
温泉直播拍顾客还拉黑质疑者 隐... 近日,有网友发帖称,上海汤连得温泉的直播间镜头长期对准洗浴区通往三楼休息区的楼梯通道。这里是顾客上下...
湖北老虎墩墓地出土漆立人凤形勺... 11月18日上午,国家文物局召开“考古中国”重大项目重要进展工作会,发布四项考古最新进展。其中,湖北...
小米回应“雷军深圳发言紧张” ... 在深圳举办的2026年APEC工商领导人峰会上,雷军分享了他对AI现状的看法。他认为技术变化迅速,但...
为何都说“APEC需要中国” ... 2026年APEC工商领导人峰会在深圳举行,吸引了21个经济体的两千多位工商界代表。峰会首日议程紧凑...
黄金会跌回400元一克吗?专家... 黄金会跌回400元一克吗?专家预测不乐观!黄金价格在2024年大幅上涨后,许多人关心2025年的走势...
东风61列装释放战略信号引发岛... 东风-61洲际导弹近日正式列装火箭军,这一消息引发了台湾岛内媒体的广泛关注。据央视网《海峡两岸》节目...
也门首都萨那传出巨大爆炸声 多... 据总台报道员消息,当地时间17日,也门首都萨那传出巨大爆炸声。另据也门胡塞武装消息,沙特阿拉伯主导的...
潮汕牛肉丸圈粉无数中外媒体记者... 潮汕牛肉丸圈粉无数中外媒体记者。11月13日,在APEC会议周新闻中心,浓郁的岭南烟火气在镜头与键盘...
哈啰单车新车型被吐槽“单车刺客... 近日,有网友在北京一路口扫到一辆蓝色新款哈啰单车,页面显示骑行30分钟收费15元,价格远高于普通共享...
女子蹲金价1年不到3万拿下32... “低价加工黄金,只要30元!”近日,在浙江湖州长兴的乡间小路上,这声吆喝吸引了村民刘大妈的注意。远低...
女子腿被压车轮下旁边女子竟指挥... 11月16日(发布),一段网友发布的视频引发热议。视频中,一名女子腿部被压在车轮下,趴在地上痛苦不已...
油价或再下调 今日价格 新一轮... 油价或再下调 今日价格 新一轮调价窗口将启。11月首调油价大跌后,新一轮油价调整有望继续下降。调整窗...
医生建议最近穿袜子睡觉:入睡快... 最近降温,每天晚上钻进被窝就像钻进“冰窖”——躺了半天双脚还是凉的。很多人觉得忍忍就好了,或等睡着就...
陆毅女儿宣布出道,“爸爸去哪儿... 继黄磊女儿10月时尚活动完成“内娱首秀”、郭涛儿子11月入选电影频道2026“星辰大海”青年演员优选...
14岁男孩带内耗妈妈运动治好内... 近日,山东菏泽。一段孩子陪妈妈运动,并喊着:“内耗的妈妈养不出明媚的孩子”的视频火了。记者联系上视频...
新娘强忍泪水与兄弟姐妹吃“分家... 广东汕尾。按照当地习俗,婚礼上新娘与兄弟姐妹吃“分家饭”,新娘强忍泪水,弟弟崩溃大哭,妹妹不敢直视姐...
消防员被困电梯名场面 网友:主... 近日,成都消防开展工作室意外被困电梯于是求救,赶来救援的同行忍不住现场“无情嘲笑”。网友:主打一个自...