当前位置: 首页 > 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;您需要选择那些在训练强大且准确的模型方面提供最大价值的图…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...