[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

相关文章

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大