当前位置: 首页 > news >正文

搜索与图论:匈牙利算法

将所有点分成两个集合,使得所有边只出现在集合之间,就是二分图

二分图:一定不含有奇数个点数的环;可能包含长度为偶数的环, 不一定是连通图

二分图的最大匹配:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;//邻接表
bool st[N];
int match[N];void add(int a , int b)
{//头插法//如图 如1与2之间要有一条线,让2的ne为1,再让h[1]为2的索引。//这样h[1]就是1节点存的最后一个相连的点,如图就是7节点。//而在索引表内部,通过头插法的方式(即每次ne指向上一个点(h存的就是上一个点)),索引表为:7->4->2e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}int find(int x)
{//遍历自己喜欢的女孩for(int i = h[x] ; i != -1 ;i = ne[i]){int j = e[i];if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定{st[j] = true;//那x就预定这个女孩了,这里预定是防止她男朋友找其他喜欢的女孩时不重复找这个//如果女孩j没有男朋友,或者她原来的男朋友能够预定其它喜欢的女孩。配对成功if(!match[j]||find(match[j])){match[j] = x;return true;}}}//自己中意的全部都被预定了。配对失败。return false;
}int main()
{memset(h,-1,sizeof h);scanf("%d%d%d",&n1,&n2,&m);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);if(find(i)) res++;//找到一条边,则res++}  printf("%d\n",res);
}

相关文章:

搜索与图论:匈牙利算法

将所有点分成两个集合&#xff0c;使得所有边只出现在集合之间&#xff0c;就是二分图 二分图&#xff1a;一定不含有奇数个点数的环&#xff1b;可能包含长度为偶数的环&#xff0c; 不一定是连通图 二分图的最大匹配&#xff1a; #include<iostream> #include<cs…...

明星艺人类的百度百科怎么创建 ?

明星艺人们的知名度对于其事业的成功至关重要&#xff0c;而作为国内最大的中文百科全书网站&#xff0c;百度百科成为了人们获取信息的重要来源。一线明星当然百科不用自己操心&#xff0c;平台和网友就给维护了&#xff0c;但是刚刚走红的明星艺人应提早布局百科词条&#xf…...

类EMD的“信号分解方法”及MATLAB实现(第八篇)——离散小波变换DWT(小波分解)

在之前的系列文章里&#xff0c;我们介绍了EEMD、CEEMD、CEEMDAN、VMD、ICEEMDAN、LMD、EWT&#xff0c;我们继续补完该系列。 今天要讲到的是小波分解&#xff0c;通常也就是指离散小波变换&#xff08;Discrete Wavelet Transform, DWT&#xff09;。在网上有一些介绍该方法…...

python随手小练10(南农作业题)

题目1&#xff1a; 编写程序&#xff0c;输出1~1000之间所有能被4整除&#xff0c;但是不能被5整除的数 具体操作&#xff1a; for i in range(1,1000): #循环遍历1~999&#xff0c;因为range是左闭右开if (i % 4 0) and (i % 5 ! 0) :print(i) 结果展示&#xff1a; 题目2&…...

How to install mongodb-7.0 as systemd service with podman

How to install mongodb-7.0 as systemd service with podman 1、安装1.1、创建卷1.2、配置文件1.3、创建容器1.4、服务管理1.5、容器管理 2、客户端管理 1、安装 1.1、创建卷 配置卷 podman volume create --label typemongo-7.0 --label envdev mongo-7.0-conf数据卷 pod…...

一文彻底理解python浅拷贝和深拷贝

目录 一、必备知识二、基本概念三、列表&#xff0c;元组&#xff0c;集合&#xff0c;字符串&#xff0c;字典浅拷贝3.1 列表3.2 元组3.3 集合3.4 字符串3.5 字典3.6 特别注意浅拷贝总结 四、列表&#xff0c;元组&#xff0c;集合&#xff0c;字符串&#xff0c;字典深拷贝 一…...

什么是软件的生命周期?全方位解释软件的生命周期

软件的生命周期 软件生命周期是指从软件产品的设想开始到软件不再使用而结束的时间。 如果把软件看成是有生命的事 物&#xff0c;那么软件的生命周期可以分成6个阶段&#xff0c;即需求分析、计划、设计、编码、测试、运行维护 需求分析阶段&#xff1a; 分析需求的可行性&…...

网络安全—小白自学

1.网络安全是什么 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 2.网络安全市场 一、是市场需求量高&#xff1b; 二、则是发展相对成熟…...

List 3.5 详解原码、反码、补码

前言 欢迎来到我的博客&#xff0c;我是雨空集&#xff08;全网同名&#xff09;&#xff0c;无论你是无意中发现我&#xff0c;还是有意搜索而来&#xff0c;我都感到荣幸。这里是一个分享知识、交流想法的平台&#xff0c;我希望我的博客能给你带来帮助和启发。如果你喜欢我…...

数据清洗与规范化详解

数据处理流程&#xff0c;也称数据处理管道&#xff0c;是将原始数据转化为有意义的信息和知识的一系列操作步骤。它包括数据采集、清洗、转换、分析和可视化等环节&#xff0c;旨在提供有用的见解和决策支持。在数据可视化中数据处理是可视化展示前非常重要的一步&#xff0c;…...

Ansible playbook的block

环境 控制节点&#xff1a;Ubuntu 22.04Ansible 2.10.8管理节点&#xff1a;CentOS 8 block 顾名思义&#xff0c;通过block可以把task按逻辑划分到不同的“块”里面&#xff0c;实现“块操作”。此外&#xff0c;block还提供了错误处理功能。 task分组 下面的例子&#x…...

Jupyter Notebook还有魔术命令?太好使了

在Jupyter Notebooks中&#xff0c;Magic commands&#xff08;以下简称魔术命令&#xff09;是一组便捷的功能&#xff0c;旨在解决数据分析中的一些常见问题&#xff0c;可以使用%lsmagic 命令查看所有可用的魔术命令 插播&#xff0c;更多文字总结指南实用工具科技前沿动态…...

DailyRecord-231029

iOS&前端&#xff1a; 数组 iOS/Xcode异常:对象数组NSMutableArray添加元素-addObject&#xff0c;但count方法仍然返回0? - 周文 - 博客园&#xff08;需要初始化&#xff09; [__NSArrayI addObject:]: unrecognized selector sent to instance &#xff08;检查addObj…...

雨云虚拟主机使用教程WordPress博客网站搭建教程

雨云虚拟主机(RVH)使用教程与宝塔面板搭建WordPress博客网站的教程&#xff0c;本文会讲解用宝塔面板一键部署以及手动安装两种方式来搭建WordPress博客&#xff0c;选其中一种方式即可。 WordPress WordPress是使用PHP语言开发的博客平台&#xff0c;用户可以在支持PHP和MyS…...

【SPSS】基于RFM+Kmeans聚类的客户分群分析(文末送书)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…...

回溯法(1)--装载问题和0-1背包

一、回溯法 回溯法采用DFS&#xff0b;剪枝的方式&#xff0c;通过剪枝删掉不满足条件的树&#xff0c;提高本身作为穷举搜索的效率。 回溯法一般有子集树和排列树两种方式&#xff0c;下面的装载问题和01背包问题属于子集树的范畴。 解空间类型&#xff1a; 子集树&#xff1…...

[javaweb]——HTTP请求与响应协议,常见响应状态码(如:404)

&#x1f308;键盘敲烂&#xff0c;年薪30万&#x1f308; 目录 HTTP概述 &#x1f4d5;概念&#xff1a;Hyper Text Transfer Protocol&#xff0c;超文本传输协议&#xff0c;规定了浏览器和服务器之间数据传输的规则。 &#x1f4d5;特点&#xff1a; &#x1f4d5;插播…...

Java面向对象(进阶)-- 拼电商客户管理系统(康师傅)

文章目录 一、目标二、需求说明&#xff08;1&#xff09;主菜单&#xff08;2&#xff09;添加客户&#xff08;3&#xff09;修改客户&#xff08;4&#xff09;删除客户&#xff08;5&#xff09;客户列表 三、软件设计结构四、类的设计&#xff08;1&#xff09;Customer类…...

Qt配置OpenCV教程,亲测已试过

详细版可参考&#xff1a;Qt配置OpenCV教程&#xff0c;亲测已试过&#xff08;详细版&#xff09;_qt opencv_-_Matrix_-的博客-CSDN博客 软件准备&#xff1a;QtOpenCVCMake (QtOpenCV安装不说了&#xff0c;CMake的安装&#xff0c;我用的是&#xff1a;可参考博客&#x…...

【实用网站分享】

1、PyDebloatX https://pydebloatx.com/pydebloatx 是一种用于 Windows 操作系统的 Python 脚本&#xff0c;用于卸载 Windows 10 系统中的预装应用和系统组件&#xff0c;以便提高系统性能和释放磁盘空间。它是 Debloat Windows 10 脚本的一个分支&#xff0c;但具有更友好和…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...