[C++][算法基础]二分图的最大匹配(匈牙利算法)

给定一个二分图,其中左半部包含 n1 个点(编号 1∼n1),右半部包含 n2 个点(编号 1∼n2),二分图共包含 m 条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配:给定一个二分图 G,在 G 的一个子图 M 中,M 的边集 {E} 中的任意两条边都不依附于同一个顶点,则称 M 是一个匹配。

二分图的最大匹配:所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配,其边数即为最大匹配数。

输入格式

第一行包含三个整数 n1、 n2 和 m。

接下来 m 行,每行包含两个整数 u 和 v,表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。

输出格式

输出一个整数,表示二分图的最大匹配数。

数据范围

1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤10^{5}

输入样例:
2 2 4
1 1
1 2
2 1
2 2
输出样例:
2

代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 510,M = 100010;
int n1,n2,m,a,b,idx,ans;
int StartNode[N],NextNode[M],Edgeto[M];
int match[N];
int att[N];


void add(int a,int b){
    Edgeto[idx] = b;
    NextNode[idx] = StartNode[a];
    StartNode[a] = idx;
    idx++;
}

int find(int x){
    for(int i = StartNode[x];i != -1;i = NextNode[i]){
        int j = Edgeto[i];
        if(att[j] == 0){
            att[j] = 1;
           if(match[j] == 0 ||find(match[j]) == 1){
               match[j] = x;
               return 1;
           }
        }
    }
    return 0;
}

int main(){
    cin>>n1>>n2>>m;
    memset(StartNode, -1, sizeof StartNode);
    while(m--){
        cin>>a>>b;
        add(a,b);
    }
    for(int i = 1;i <= n1;i ++){
        memset(att, 0, sizeof att);
        if(find(i) == 1){
            ans ++;
        }
    }
    cout<<ans;
    return 0;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/550191.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

天池酒瓶瑕疵检测数据集分析及完整baseline

以下内容为还没思路的小伙伴牵个头提供一个demo,大佬勿喷,线上成绩0.7,留空间给小伙伴们发挥自己的力量 ps:markdown不怎么熟悉,代码中如有明显缩进问题,自行斟酌改正,编辑好几次都改不过来,请原谅.... 数据分析瑕疵大类: 瓶盖瑕疵、标贴瑕疵、喷码瑕疵、瓶身瑕疵、酒液瑕疵瑕…

会议室预约小程序开源版开发

会议室预约小程序开源版开发 支持设置免费预约和付费预约、积分兑换商城、积分签到等 会议室类目&#xff0c;提供多种类型和设施的会议室选择&#xff0c;满足不同会议需求。 预约日历&#xff0c;展示会议室预约情况&#xff0c;方便用户选择空闲时段。 预约记录&#xff0…

机器学习实验------决策树

第1关&#xff1a;什么是决策树 任务描述 本关任务&#xff1a;根据本节课所学知识完成本关所设置的选择题。 第2关&#xff1a;信息熵与信息增益 任务描述 本关任务&#xff1a;掌握什么是信息增益&#xff0c;完成计算信息增益的程序设计。 import numpy as npdef calcIn…

聚道云软件连接器助力企业实现滴滴出差报销自动化

一、客户介绍 某机械有限公司是一家在机械设备制造领域拥有深厚底蕴和卓越实力的企业。自公司成立以来&#xff0c;该公司始终秉承创新、务实、高效的发展理念&#xff0c;专注于机械设备的研发、生产和销售。经过多年的发展&#xff0c;公司已成为国内机械行业的佼佼者&#…

在Qt中如何简单设计一个文件和图像浏览器

文本浏览器 设计一个文本浏览器程序&#xff0c;可以打开、显示 txt、html等文件。 1.在Qt Designer中设计一个菜单其中包含打开和退出选项&#xff1a; 2. 在 QMainWindow 构造函数中把 textBrower 设为主窗口的中心部件&#xff0c;这样整个窗口就成了包含 textBrower 的单文…

书生·浦语2.0(InternLM2)大模型实战--Day04 XTuner微调 | 1.8B 多模态Agent

视频地址&#xff1a; https://b23.tv/QUhT6ni课程文档&#xff1a;https://github.com/InternLM/Tutorial/blob/camp2/xtuner/readme.md作业文档&#xff1a;https://github.com/InternLM/Tutorial/blob/camp2/xtuner/homework.md XTuner 微调个人小助手认知 在本节课中讲一步…

SQL刷题---2021年11月每天新用户的次日留存率

解题思路&#xff1a; 1.首先算出每个新用户注册的日期,将其命名为表a select uid,min(date(in_time)) dt from tb_user_log group by uid2.计算出每个用户登录的天数,将其命名为表b select uid,date(in_time) dt from tb_user_log union select uid,date(out_time) dt fro…

linux C -- 消息队列

linux C -- 消息队列 前言一、System V(IPC)消息队列接口调用主要涉及到 msgget、msgsnd、msgrcv 和 msgctl 四个接口&#xff1a; 1、创建消息队列 msgget2、发送消息到队列3、从队列接收信息4、控制消息队列 msgctl5、删除消息队列 二、代码编写1、发送部分的代码2、代码完成…

扭蛋机市场如何?全新淘宝扭蛋机小程序发展前景

近几年&#xff0c;扭蛋机市场发展的非常迅速&#xff0c;市场发展前景也在不断扩大。随着人们的生活水平提高&#xff0c;对娱乐消费也更加青睐&#xff0c;尤其是具有刺激性、惊喜性的消费模式。而扭蛋机具备的优势刚好符合大众对娱乐消费的要求&#xff0c;因此&#xff0c;…

Kafka服务端(含Zookeeper)一键自启软件

1. 前言 本文介绍了一款集成图形化界面配置和一键自启功能的Kafka与Zookeeper服务管理软件。该软件通过直观易用的图形界面&#xff0c;使用户能够轻松完成Kafka和Zookeeper的配置工作&#xff0c;有效避免了手动编辑配置文件可能带来的错误和不便。同时&#xff0c;软件还提供…

TCP网络程序

上一章我们基于UDP实现了几个网络程序&#xff0c;这一章我们开始使用TCP。 先简单复习一下TCP和UDP的特点&#xff1a; TCP特点 传输层协议有连接可靠传输面向字节流 UDP特点 传输层协议无连接不可靠传输面向数据报 可以看到TCP是有链接的&#xff0c;而UDP是无连接的&#…

简单3步,OpenHarmony上跑起ArkUI分布式小游戏

标准系统新增支持了方舟开发框架&#xff08;ArkUI&#xff09;、分布式组网和 FA 跨设备迁移能力等新特性&#xff0c;因此我们结合了这三种特性使用 ets 开发了一款如下动图所示传炸弹应用。 打开应用在通过邀请用户进行设备认证后&#xff0c;用户须根据提示完成相应操作&am…

2024-14.python前端+Django

第四篇 web前端 第1章 、Web的基本概念 前端基础总共分为三部分&#xff1a;html、css和js。 1.3、HTTP协议 1.3.1 、http协议简介 HTTP协议是Hyper Text Transfer Protocol&#xff08;超文本传输协议&#xff09;的缩写,是用于万维网&#xff08;WWW:World Wide Web &am…

神经网络压缩图像

简介 典型的压缩管道由四个组件组成&#xff1a; 编码&#xff1a;输入图像 x x x通过编码器函数 ε \varepsilon ε&#xff0c;将其转换为潜在表示 z z z。 量化&#xff1a;截断 z z z以丢弃一些不重要的信息 熵编码&#xff1a;使用某种形式的熵编码&#xff08;例如&…

淘宝API商品详情数据在数据分析行业中具有不可忽视的重要性

淘宝商品详情数据在数据分析行业中具有不可忽视的重要性。这些数据为商家、市场分析师以及数据科学家提供了丰富的信息&#xff0c;有助于他们更深入地理解市场动态、消费者行为以及商品竞争态势。以下是淘宝商品详情数据在数据分析行业中的重要性体现&#xff1a; 请求示例&a…

OpenStack 入门体验

目录 一、云计算概述 1.1、什么是云计算 1.2、云计算的服务模型 1&#xff09;IaaS 2&#xff09;PaaS 3&#xff09;SaaS 1.3、OpenStack 概述 1&#xff09;OpenStack 起源 2&#xff09;什么是 OpenStack 3&#xff09;OpenStack 优势 二、OpenStack 一…

基于JavaWeb开发的springboot网约车智能接单规划小程序[附源码]

基于JavaWeb开发的springboot网约车智能接单规划小程序[附源码] &#x1f345; 作者主页 央顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; &#x1f345; 查看下方微信号获取联系方式 承接各种…

Java项目如何使用EasyExcel插件对Excel数据进行导入导出

文章目录 一、EasyExcel的示例导入依赖创建实体类数据导入和导出 二、EasyExcel的作用三、EasyExcel的注解 EasyExcel是一个阿里巴巴开源的excel处理框架&#xff0c;它以使用简单、节省内存著称。在解析Excel时&#xff0c;EasyExcel没有将文件数据一次性全部加载到内存中&…

使用 Flask 和 Flask-Login 构建用户认证的 Web 应用程序

在本篇技术博客中&#xff0c;我们将学习如何使用 Flask 框架和 Flask-Login 扩展构建一个具有用户认证功能的简单 Web 应用程序。我们将从创建 Flask 应用实例开始&#xff0c;然后逐步添加用户认证功能。 1. 安装依赖库 首先&#xff0c;确保您已经安装了 Flask、Flask-PyM…

大模型微调的几种常见方法

在文章深入理解大语言模型微调技术中&#xff0c;我们详细了解大语言模型微调的概念和训练过程&#xff0c;本篇给大家介绍大模型微调常见的7种训练方法。 1、Adapter Tuning 2019年谷歌的研究人员首次在论文《Parameter-Efficient Transfer Learning for NLP》提出针对 BERT 的…