[AcWing]861. 二分图的最大匹配(C++实现)匈牙利算法匹配二分图模板题

2024-03-27 10:20

本文主要是介绍[AcWing]861. 二分图的最大匹配(C++实现)匈牙利算法匹配二分图模板题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[AcWing]861. 二分图的最大匹配(C++实现)匈牙利算法匹配二分图模板题

  • 1. 题目
  • 2. 读题(需要重点注意的东西)
  • 3. 解法
  • 4. 可能有帮助的前置习题
  • 5. 所用到的数据结构与算法思想
  • 6. 总结

1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

思路:
首先要知道,什么是二分图。

二分图的定义如下: 二分图又称作二部图,是图论中的一种特殊模型。
设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i
in A,j in B),则称图G为一个二分图。
简而言之:如果把无向图中的节点划分为两个互不相交的子集,图中一条边的两个端点分别属于这两个集合,这样的图就叫二分图。

匈牙利算法匹配的主要思想是:
当发生匹配冲突时,看能否解决冲突,能的话就返回true,皆大欢喜;否则就返回false。匹配算法的流程如下图所示:
在这里插入图片描述

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 510, M = 100010;int n1, n2, m;
int h[N], e[M], ne[M], idx; // 稀疏图用邻接表存储
int match[N];
bool st[N]; // st数组判重,即不要重复搜一个点void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}// 找给出的节点x能否配对
bool find(int x){for(int i = h[x];i != -1;i = ne[i]){int j = e[i]; // j是n2集合的一个数if(st[j] == 0){ // 如果j没考虑过,考虑它st[j] = 1; // j考虑过了,不重复考虑if(match[j] == 0 || find(match[j])){ // 如果j未配对,或者与j配对的值(在n1集合中)能再找一个值配对match[j] = x; // 则这个j与x配对return true; // 成功配对一组}}}return false;
}int main()
{scanf("%d%d%d", &n1, &n2, &m);memset(h, -1, sizeof h);while (m -- ){int a, b;scanf("%d%d", &a, &b);add(a, b);}int res = 0;for (int i = 1; i <= n1; i ++ ){memset(st, false, sizeof st); // 每次都要将st数组置位0,表示没有考虑过所有的节点if (find(i)) res ++ ; // 如果能成功配对,res加1表示成功配对的组数加1}printf("%d\n", res);return 0;
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

  • 邻接表存储稀疏图

6. 总结

匈牙利算法计算二分图的最大匹配的模板题,背下来!

这篇关于[AcWing]861. 二分图的最大匹配(C++实现)匈牙利算法匹配二分图模板题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/851778

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、