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

acwing算法基础之搜索与图论--匈牙利算法求二分图的最大匹配数

目录

  • 1 基础知识
  • 2 模板
  • 3 工程化

1 基础知识

二分图中的最大匹配数:从二分图中选择一些边(这些边连接集合A和集合B,集合A中结点数目为n1,集合B中结点数目为n2),设为集合S,其中任意两条边不共用一个结点。求集合S的最大元素数目,即二分图中的最大匹配数。

匈牙利算法的关键步骤:

  1. 初始化匹配数组match[1~n2] = 0。其中match[b] = a,表示集合B中的结点b匹配了集合A中的结点a。
  2. 遍历集合A中的每一个结点a:初始化状态数组st[1~n2] = false,其中st[b] = false表示集合B中的结点b没有被访问。然后,find(x),如果它返回true,那么答案加1。
bool find(int a) {//a为集合A中的结点for (auto b : g[x]) {if (!st[b]) {//如果结点b没有被访问st[b] = true;if (match[b] == 0 || find(match[b])) { //如果结点b没有被匹配,或者结点b匹配了的结点可以找到新的match[b] = a;return true;}}}return false;
}
  1. 最终返回答案,即为该二分图的最大匹配数。

2 模板

int n1, n2;     // n1表示第一个集合中的点数,n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边,匈牙利算法中只会用到从第一个集合指向第二个集合的边,所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过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;}}}return false;
}// 求最大匹配数,依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{memset(st, false, sizeof st);if (find(i)) res ++ ;
}

3 工程化

题目1:求二分图的最大匹配。

#include <iostream>
#include <cstring>
#include <vector>using namespace std;const int N = 510;
int n1, n2, m;
vector<vector<int>> g(N);
int match[N];
bool st[N];bool find(int a) {for (auto b : g[a]) {if (!st[b]) {st[b] = true;if (match[b] == 0 || find(match[b])) {match[b] = a;return true;}}}return false;
}int main() {cin >> n1 >> n2 >> m;int a, b;while (m--) {cin >> a >> b;g[a].emplace_back(b);}int res = 0;for (int i = 1; i <= n1; ++i) {memset(st, 0, sizeof st);if (find(i)) res++;}cout << res << endl;return 0;
}

相关文章:

acwing算法基础之搜索与图论--匈牙利算法求二分图的最大匹配数

目录 1 基础知识2 模板3 工程化 1 基础知识 二分图中的最大匹配数&#xff1a;从二分图中选择一些边&#xff08;这些边连接集合A和集合B&#xff0c;集合A中结点数目为n1&#xff0c;集合B中结点数目为n2&#xff09;&#xff0c;设为集合S&#xff0c;其中任意两条边不共用一…...

优化重复冗余代码的8种方式

文章目录 前言1、抽取公用方法2、抽工具类3、反射4、泛型5、继承与多态6、使用设计模式7、自定义注解(或者说AOP面向切面)8、函数式接口和Lambda表达式 前言 日常开发中&#xff0c;我们经常会遇到一些重复代码。大家都知道重复代码不好&#xff0c;它主要有这些缺点&#xff…...

DVWA - 3

文章目录 XSS&#xff08;Dom&#xff09;lowmediumhighimpossible XSS&#xff08;Dom&#xff09; XSS 主要基于JavaScript语言进行恶意攻击&#xff0c;常用于窃取 cookie&#xff0c;越权操作&#xff0c;传播病毒等。DOM全称为Document Object Model&#xff0c;即文档对…...

android studio离线tips

由于种种原因&#xff08;你懂的&#xff0c;导致我们使用android studio会有很多坑&#xff0c;这里记录一下遇到的问题以及解决方案 环境问题 无法下载gradle 因为android studio采用gradle作为构建工具&#xff0c;国内gradle没有镜像下载非常慢&#xff0c;并且大概率失…...

JWT概念(登录代码实现)

JWT (JSON Web Token)是一种开放标准&#xff0c;用于在网络应用程序之间安全地传输信息。JWT是一种基于JSON的轻量级令牌&#xff0c;包含了一些声明和签名&#xff0c;可以用于认证和授权。 JWT主要由三部分组成&#xff1a;头部、载荷和签名。 头部包含了使用的算法和类型…...

如何在 Windows 10/11 上高质量地将 WAV 转换为 MP3

WAV 几乎完全准确地存储了录音硬件所听到的内容&#xff0c;这使得它变得很大并占用了更多的存储空间。因此&#xff0c;WAV 格式在作为电子邮件附件发送、保存在便携式音频播放器上、通过蓝牙或互联网从一台设备传输到另一台设备等时可能无法正常工作。 如果您遇到 WAV 问题&…...

详解FreeRTOS:FreeRTOS消息队列(高级篇—1)

目录 1、队列简介 2、队列的运行机制 3、队列的阻塞机制 4、队列结构体 5、创建队列...

Vue3 + ts+ elementUi 实现后台数据渲染到下拉框选项中,滑动加载更多数据效果

前言 功能需求&#xff1a;下拉框中分页加载后端接口返回的人员数据&#xff0c;实现滑动加载更多数据效果&#xff0c;并且可以手动搜索定位数据&#xff0c;此项目使用Vue3 ts elementUi 实现 实现 把此分页滑动加载数据功能封装成vue中的hooks&#xff0c;文件命名为use…...

Elasticsearch 索引库操作与 Rest API 使用详解

1. 引入 Elasticsearch 依赖 在开始之前&#xff0c;确保你的 Maven 或 Gradle 项目中已经引入了 Elasticsearch 的 Java 客户端库。你可以使用以下 Maven 依赖&#xff1a; xml <dependency> <groupId>org.elasticsearch.client</groupId> <ar…...

线性代数(四)| 解方程 齐次性 非齐次性 扩充问题

文章目录 1 方程解的个数2 解方程步骤2.1 齐次性方程组2.2 非齐次方程组 3 一些扩充问题 系数矩阵 增广矩阵 A m n X B A_{mn}XB Amn​XB 1 方程解的个数 m 代表有m个方程 n代表有n个未知数 系数矩阵的秩与增广矩阵的秩不同 无解 若相同 &#xff0c;如系数矩阵的秩和未知…...

快乐数问题

编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为&#xff1a; 对于一个正整数&#xff0c;每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1&#xff0c;也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1&#xff…...

8 历史服务器配置

为了查看程序的历史运行情况&#xff0c;需要配置一下历史服务器 1、配置mapred-site.xml vim mapred-site.xml在该文件里面增加如下配置 //原先的配置不用删除 <!-- 历史服务器端地址 --> <property><name>mapreduce.jobhistory.address</name><…...

读书笔记:《精益数据分析》

《精益数据分析 . Lean Analytics Use Data to Build a Better Startup Faster》 加 . 阿利斯泰尔 . 克罗尔 本杰明 . 尤科维奇 著&#xff0c;韩知白 王鹤达 译 2023.7.27 ~ 2023.11.4 本以为是本纯数学的、介绍公式的数据分析用法的书&#xff0c;结果是&#xff1a;…...

酷柚易汛ERP- 组装单与拆卸单操作

1、功能介绍 组装单用来处理企业组装等加工业务&#xff0c;拆卸单用来处理企业拆卸等加工业务&#xff0c;支持一对多的产品加工业务。 2、主要操作 2.1 新增组装单 打开【仓库】-【组装单】新增组装单。 录入组合件与子件&#xff0c;单据审核后&#xff0c;系统根据存货…...

yolov8训练

介绍 训练深度学习模型包括向其提供数据并调整其参数&#xff0c;以便其能够做出准确的预测。Ultralytics YOLOv8中的训练模式旨在充分利用现代硬件功能&#xff0c;对目标检测模型进行有效和高效的训练。本指南旨在涵盖使用YOLOv8强大的一组功能开始训练自己的模型所需的所有细…...

抖音短视频账号矩阵系统、短视频矩阵源码+无人直播源码开发可打包

抖音短视频账号矩阵系统、短视频矩阵源码无人直播源码开发可打包 矩阵系统源码主要有三种框架&#xff1a;Spring、Struts和Hibernate。Spring框架是一个全栈式的Java应用程序开发框架&#xff0c;提供了IOC容器、AOP、事务管理等功能。Struts框架是一个MVC架构的Web应用程序框…...

NI和EttusResearchUSRP设备之间的区别

NI和EttusResearchUSRP设备之间的区别 概述 USRP&#xff08;通用软件无线电外设&#xff09;设备是业界领先的商软件定义无线电&#xff08;SDR&#xff09;。全球数以千计的工程师使用USRPSDR来快速设计、原型设计和部署无线系统。它们以两个不同的品牌进行营销和销售&…...

WPF UI样式介绍

WPF&#xff08;Windows Presentation Foundation&#xff09;是微软的一个用于创建桌面客户端应用程序的UI框架。WPF使用XAML&#xff08;可扩展应用程序标记语言&#xff09;作为其界面设计语言&#xff0c;这使得开发者能够以声明性方式定义UI元素和布局。 在WPF中&#xf…...

【开源】基于Vue.js的校园失物招领管理系统的设计和实现

目录 一、摘要1.1 项目介绍1.2 项目详细录屏 二、研究内容2.1 招领管理模块2.2 寻物管理模块2.3 系统公告模块2.4 感谢留言模块 三、界面展示3.1 登录注册3.2 招领模块3.3 寻物模块3.4 公告模块3.5 感谢留言模块3.6 系统基础模块 四、免责说明 一、摘要 1.1 项目介绍 基于Vue…...

计算机视觉中目标检测的数据预处理

本文涵盖了在解决计算机视觉中的目标检测问题时&#xff0c;对图像数据执行的预处理步骤。 首先&#xff0c;让我们从计算机视觉中为目标检测选择正确的数据开始。在选择计算机视觉中的目标检测最佳图像时&#xff0c;您需要选择那些在训练强大且准确的模型方面提供最大价值的图…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...