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

【AcWing】861. 二分图的最大匹配(匈牙利算法)

匈牙利算法,他可以在比较快的时间复杂度之内告诉我们左边和右边成功匹配的最大数是多少

匹配指的是边的数量,成功的匹配指的是两个未被使用的点之间存在一条边(就不存在两条边共用了一个点的)。

匈牙利算法可以返回成功匹配的最大匹配数是多少。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N=510,M=1e5+10;
int h[N],e[M],ne[M],idx;
int match[N];//match表示的是这个妹子匹配的男生是谁,0代表没有匹配。
bool st[N];//表示这个女生是否考虑过
int n1,n2,m;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])){//妹子没有匹配的男生 或 这个男生可以找到其他的妹子代替//如果这个被替换妹子的男生的其他相连的女生被匹配了的话,会让匹配的那个男生再去找其他妹子,就是套娃,牵一发动所有有关系的人。每个男生进入find都会对已经被考虑的妹子变为true,不会造成重复考虑。match[j]=x;return true;   }}}return false;
}int main(){cin>>n1>>n2>>m;memset(h,-1,sizeof h);while(m--){int a,b;cin>>a>>b;add(a,b);//虽然是无向边,但只会找一下左边点的所有出边,只需要存左边指向右边就可以了。}int res=0;//匹配数量//就依次来分析一下每个男生,该找哪个妹子。for(int i=1;i<=n1;i++){memset(st,false,sizeof st);//每一次分析之前,清空所有妹子,表示这些妹子都还没考虑过,保证每个妹子我只考虑一遍。if(find(i)) res++;//判断是否能找到妹子}cout<<res<<endl;return 0;
}

相关文章:

【AcWing】861. 二分图的最大匹配(匈牙利算法)

匈牙利算法&#xff0c;他可以在比较快的时间复杂度之内告诉我们左边和右边成功匹配的最大数是多少 匹配指的是边的数量&#xff0c;成功的匹配指的是两个未被使用的点之间存在一条边(就不存在两条边共用了一个点的)。 匈牙利算法可以返回成功匹配的最大匹配数是多少。 #incl…...

经验笔记:JSP(JavaServer Pages)

JSP&#xff08;JavaServer Pages&#xff09;经验笔记 JSP&#xff08;JavaServer Pages&#xff09;是一种用于创建动态网页的技术&#xff0c;它允许在HTML页面中嵌入Java代码&#xff0c;从而实现动态内容的生成。JSP与Servlet一样&#xff0c;都是Java EE平台的一部分&am…...

【零基础必看的数据库教程】——SQL WHERE 子句

WHERE 子句用于提取那些满足指定条件的记录&#xff0c;过滤记录。 SQL WHERE 语法&#xff1a; SELECT column1, column2, ... FROM table_name WHERE condition; 参数说明&#xff1a; column1, column2, ...&#xff1a;要选择的字段名称&#xff0c;可以为多个字段。如…...

vscode docker debug python

1. 安装Vscode插件 ”Docker“”Dev Containers““Remote - ssh” 2. 进入Docker环境 点击左侧 Docker图标&#xff0c;选择Containers 对容器进行右键启动 生成新页面直接进行选择文件路径即可&#xff0c;之后得操作均在容器内进行...

【Kubernetes】常见面试题汇总(四)

目录 11.简述 Kubernetes 集群相关组件&#xff1f; 12.简述 Kubernetes Rc 的机制&#xff1f; 11.简述 Kubernetes 集群相关组件&#xff1f; Kubernetes Master控制组件&#xff0c;调度管理整个系统(集群)&#xff0c;包含如下组件&#xff1a; &#xff08;1&#xff…...

MATLAB基础语法知识

环境的配置等等就不写了&#xff0c;网上还是有很多资源可以找&#xff0c;而且正版的要付费&#xff0c;我也是看的网上的搞定的。 一&#xff0c;初识MATLAB 1.1 MATLAB的优势 不需要过多了解各种数值计算方法的具体细节和计算公式&#xff0c;也不需要繁琐的底层编程。可…...

PopupInner源码分析 -- ant-design-vue系列

PopupInner源码分析 – ant-design-vue系列 1 综述 上一篇讲解了vc-align的工作原理&#xff0c;也就是对齐是如何完成的。这一篇主要讲述包裹 Align的组件&#xff1a;PopupInner组件是如何工作的。 PopupInner主要是对动画状态的管理&#xff0c;比如打开弹窗的时候&#…...

Maven 的 pom.xml 文件中<dependency> 元素及其各个参数的解释

在 Maven 的 pom.xml 文件中&#xff0c;<dependency> 标签用于定义项目依赖的外部库。每个 <dependency> 元素包含了一系列的子元素&#xff0c;这些子元素定义了依赖库的各种属性。下面是一个典型的 <dependency> 元素及其各个参数的解释&#xff1a; <…...

【信创】Linux终端禁用USB存储 _ 统信 _ 麒麟 _ 方德

原文链接&#xff1a;【信创】Linux终端禁用USB存储 | 统信 | 麒麟 | 方德 Hello&#xff0c;大家好啊&#xff01;今天给大家带来一篇关于在Linux终端下禁用USB存储设备的文章。禁用USB存储设备可以提高系统的安全性&#xff0c;防止未经授权的人员将数据拷贝到外部存储设备或…...

开放API接口时要注意的安全处理总结

开发API接口&#xff1a;开放给别人调用的接口。未经过安全处理的开发API接口安全弱点&#xff1a;数据窃取&#xff08;密码等信息被窃取&#xff0c;盗刷&#xff0c;敏感信息的等&#xff09;——RSA/DES加密&#xff1a; 签名机制在API接口中的应用&#xff1a;签名用于验证…...

FastGPT自定义插件的icon

最近研究FastGPT的自定义插件&#xff0c;经过好几天的折磨&#xff0c;终于实现了一个简单的发送邮件功能&#xff0c;但是呢在使用的时候发现插件的icon是默认的fastgpt的logo&#xff0c;那肯定得自定义一个啊。直接说方法&#xff1a; 1、自定义插件下面的template.json文件…...

SprinBoot+Vue旅游网站的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍&#xff1a;CSDN认证博客专家&#xff0c;CSDN平台Java领域优质…...

代码随想录刷题day27丨455.分发饼干 ,376. 摆动序列 ,53. 最大子序和

代码随想录刷题day27丨455.分发饼干 ,376. 摆动序列 ,53. 最大子序和 1.贪心算法理论基础 贪心的本质是选择每一阶段的局部最优&#xff0c;从而达到全局最优。 这么说有点抽象&#xff0c;来举一个例子&#xff1a; 例如&#xff0c;有一堆钞票&#xff0c;你可以拿走十张&a…...

Detect It Easy

Detect It Easy&#xff08;简称 DIE&#xff09;项目的网址为 https://github.com/horsicq/Detect-It-Easy 下载完安装包后&#xff0c;直接双击die.exe即可进入到操作界面 工具介绍&#xff1a; 它可以用来检测程序架构和文件类型。如图所示。其中&#xff0c;「模式」说明程…...

c++开关灯

题目描述 现有 &#x1d45b;n 盏灯排成一排&#xff0c;从左到右依次编号为&#xff1a;11&#xff0c;22&#xff0c;……&#xff0c;&#x1d45b;n。然后依次执行 &#x1d45a;m 项操作。 操作分为两种&#xff1a; 指定一个区间 [&#x1d44e;,&#x1d44f;][a,b]&…...

DevOps实现CI/CD实战(六)- Jenkins集成k8s

十、 Jenkins集成k8s Jenkins在集成K8s之前&#xff0c;需要搭建k8s集群&#xff0c;具体搭建步骤&#xff0c;完整笔记 https://github.com/ITenderL/ITenderL.github.io/tree/main/docs/DevOps&#xff0c; 包括完整的DevOps的笔记。 1. 准备部署的yml文件 pipeline.yml …...

张雪峰:物联网行业迎高光时刻!如何选择?我们诚聘销售工程师!

作为一间10多年的物联网公司&#xff0c;各位求职人士可以看看我们其中一个招聘要求&#xff0c;和自己需求结合分析分析&#xff0c;希望对你们有所帮助。 【公司实力底蕴】 盈电智控物联网科技&#xff08;广东&#xff09;有限公司&#xff0c;2024年7月成立&#xff0c;是…...

利用多文件编程实现顺序表的创建,判满,插入,输出

文章目录 &#x1f34a;自我介绍&#x1f34a;利用多文件编程实现顺序表的创建&#xff0c;判满&#xff0c;插入&#xff0c;输出seqlist.cseqlist.hmain.c 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以&#xff1a;点赞关注评论收藏&#xff08;一键四连&#xff…...

百度快照劫持之JS劫持诊断与恢复一例

劫持现象&#xff1a; 百度搜索结果中&#xff0c;被劫持网站出现在搜索结果中&#xff0c; 点击进入网站&#xff0c;网站显示正常&#xff0c;数秒后网站自动跳转到彩票网站f51688.com/ff6/。但是第二次点击搜索结果&#xff0c;正常进入网站缺不会跳转到彩票网站。 初步认…...

深入探讨Go语言中的切片与数组操作

在编程世界中&#xff0c;数组一直是非常流行的数据结构&#xff0c;主要有两个原因&#xff1a;其一是简单易懂&#xff0c;其二是非常灵活&#xff0c;可以存储多种不同类型的数据。在Go语言中&#xff0c;数组的用法有其独特的特点&#xff0c;但与此同时&#xff0c;Go语言…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...