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

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

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

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

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...