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

匈牙利算法模板

P3386 【模板】二分图最大匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:最模板的一集.还未匹配则匹配,否则之前一个给现在这个让位置.

int n,m,e;
vector<int> vct[505];
int match[505];
bool vis[505];
bool mark[505][505];
bool dfs(int s){for(auto v:vct[s]){if(vis[v]) continue;vis[v]=1;if(!match[v]||dfs(match[v])){   女生没有伴侣,或者其伴侣可以选择其他女生match[v]=s;return 1;}}return 0;
}
void solve(){               匈牙利🇭🇺--求最大匹配 o(n*m)cin>>n>>m>>e;for(int i=1;i<=e;i++){int u,v; cin>>u>>v;if(!mark[u][v]){vct[u].emplace_back(v);    建单向边mark[u][v]=1;}}int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) vis[j]=0;if(dfs(i)) ans++;}cout<<ans;
}

C-有大家喜欢的零食吗_河南萌新联赛2024第(一)场:河南农业大学 (nowcoder.com)

思路:纯模板.

int n;
vector<int> vct[505];
int match[505],vis[505];
bool dfs(int s){for(auto v:vct[s]){if(vis[v]) continue;vis[v]=1;if(!match[v]||dfs(match[v])){    如果女生没有伴侣,或者其伴侣可以选择其他女生match[v]=s;    糖果v被s孩子选了return 1;}}return 0;
}
有大家喜欢的零食吗
https://ac.nowcoder.com/acm/contest/86639/C
void solve(){               C   匈牙利🇭🇺--求最大匹配cin>>n;for(int i=1;i<=n;i++){int k; cin>>k;for(int j=1;j<=k;j++){      孩子选糖果int x; cin>>x;vct[i].emplace_back(x);}}int ans=0;for(int i=1;i<=n;i++){if(dfs(i)) ans++;for(int j=1;j<=n;j++) vis[j]=0; init}if(ans==n) cout<<"Yes";else cout<<"No"<<endl<<n-ans;
}

[ABC091C] 2D Plane 2N Points - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:纯模板

int n;
pair<int,int> a[150];
pair<int,int> b[150];
vector<int> vct[105];
int match[105];
bool vis[105];
bool dfs(int s){for(auto v:vct[s]){if(vis[v]) continue;vis[v]=1;if(!match[v]||dfs(match[v])){     如果女生没有伴侣,或者其伴侣可以选择其他女生match[v]=s;return 1;}}return 0;
}
2D Plane 2N Points
https://www.luogu.com.cn/problem/AT_arc092_a
void solve(){  B--匈牙利cin>>n;for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;for(int i=1;i<=n;i++) cin>>b[i].first>>b[i].second;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i].first<b[j].first&&a[i].second<b[j].second) vct[i].emplace_back(j);}}int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) vis[j]=0;if(dfs(i)) ans++;}cout<<ans;
}

相关文章:

匈牙利算法模板

P3386 【模板】二分图最大匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路:最模板的一集.还未匹配则匹配&#xff0c;否则之前一个给现在这个让位置. int n,m,e; vector<int> vct[505]; int match[505]; bool vis[505]; bool mark[505][505]; bool dfs(int s)…...

ubuntu 安装harbor

#安装包 wget https://github.com/goharbor/harbor/releases/download/v2.10.3/harbor-offline-installer-v2.10.3.tgz wget https://github.com/goharbor/harbor/releases/download/v2.10.3/harbor-offline-installer-v2.10.3.tgz.asc#导入签名公钥 gpg --keyserver hkps://ke…...

Python/大数据/机器识别毕业设计选题题目推荐

基于Python和Diango在线购物商城系统报告文档指导搭建视频 基于深度学习的人脸识别与管理系统&#xff0c;Python实现 基于Python/机器学习链家网新房数据可视化及预测系统 Python豆瓣电影情感分析推荐系统爬虫可视化&#xff0c;过滤算法 基于python的django框架生鲜商城管…...

基于Python的人工智能应用案例系列(17):LSTM正弦波预测

概述 本案例展示了如何使用LSTM&#xff08;长短期记忆网络&#xff09;来预测正弦波序列的未来值。由于正弦波具有周期性&#xff0c;传统的神经网络难以准确预测其上升或下降趋势&#xff0c;而LSTM则能够通过学习值的模式来进行更精准的预测。本案例将训练LSTM模型并预测正弦…...

Python空间地表联动贝叶斯地震风险计算模型

&#x1f3af;要点 使用贝叶斯推断模型兼顾路径和场地效应&#xff0c;量化传统地理统计曲线拟合技术。使用破裂和场地特征等地质信息以及事件间残差和事件内残差描述数学模型模型使用欧几里得距离度量、角距离度量和土壤差异性度量确定贝叶斯先验分布和后验分布参数&#xff…...

虚幻引擎-设置UI自适应屏幕大小

在游戏中&#xff0c;如果想实现不同分辨率下&#xff0c;都可以支持当前的UI界面布局&#xff0c;都需要用到锚点功能。 ‌虚幻引擎中的UI锚点&#xff08;Anchor&#xff09;是指控件在屏幕或父物体上的固定点&#xff0c;用于确定控件的位置和布局。‌ 锚点的作用是确保UI元…...

C++继承的三种方式[ACCESS]

C继承的定义 两个类的继承关系在派生类中声明&#xff0c;派生类定义使用以下语法&#xff1a; class DerivedClass: [ACCESS] BaseClass{ /…/ }; 冒号&#xff08;:&#xff09;后的[ACCESS]是继承的最高权限级别符&#xff0c;可以是以下三个值&#xff08;存取权限级别&am…...

idea 同一个项目不同模块如何设置不同的jdk版本

在IntelliJ IDEA中&#xff0c;可以为同一个项目中的不同模块设置不同的JDK版本。这样做可以让你在同一个项目中同时使用多个Java版本&#xff0c;这对于需要兼容多个Java版本的开发非常有用。以下是设置步骤&#xff1a; 打开项目设置&#xff1a; 在IDEA中&#xff0c;打开你…...

1-仙灵之谜(区块链游戏详情介绍)

1-仙灵之谜&#xff08;区块链游戏详情介绍&#xff09; 前言&#xff08;该游戏仅供娱乐&#xff09;正文 前言&#xff08;该游戏仅供娱乐&#xff09; 依稀记得本科那会儿参加了一个区块链实验室&#xff0c;那时每周末大家都会爬山或者抽出一下午讨论区块链以及未来&#x…...

基于51单片机的温湿度上下限监测预警proteus仿真

地址&#xff1a;https://pan.baidu.com/s/1hSprWBYhKKx8Txzaj33YPA?pwdjp3d 提取码&#xff1a;1234 仿真图&#xff1a; 芯片/模块的特点&#xff1a; AT89C52/AT89C51简介&#xff1a; AT89C52/AT89C51是一款经典的8位单片机&#xff0c;是意法半导体&#xff08;STMic…...

考核总结.

事件循环 单线程的js在处理异步事件时进行的一种循环过程。 在 JS中任务分为同步与异步任务&#xff0c;其中异步任务又分为两种&#xff1a;宏任务和 微任务。宏任务和微任务的执行顺序&#xff1a;总方针是先同步再异步&#xff0c;异步中先微任务&#xff0c;在宏任务。一次…...

后端学习路线

后端学习路线 一、编程语言 至少需要学习一门编程语言&#xff0c;建议学习JAVA和GO语言。 二、数据库 数据库分为关系型数据库和非关系型数据库&#xff0c;区别在于分关系型数据库常用于大数据&#xff0c;而非关系型数据库一般不在大数据方面使用。 关系型数据库&#x…...

车辆重识别(注意力 U-Net:学习在哪些区域寻找胰腺)论文阅读2024/10/01

什么是注意力机制&#xff1f; 什么是加性注意力&#xff1f; 大致说一下流程&#xff1a; 对于一张特征图来说&#xff0c;对于这张图中的每一个像素向量&#xff08;例如a&#xff09;&#xff0c;计算该向量与所有像素向量的相似度&#xff0c;对这些相似度进行激活函数…...

【区别】git restore --staged <文件> 和 git reset HEAD <文件> 都可以用于取消已暂存的文件

git restore --staged <文件> 和 git reset HEAD <文件> 都可以用于取消已暂存的文件&#xff0c;但它们的工作原理和适用场景有所不同。以下是对这两个命令的详细比较&#xff1a; 1. 命令概述 git restore --staged <文件>&#xff1a; 专门用于将指定文件…...

void类型

编程语言中的void类型是一种特殊的数据类型&#xff0c;它表示不存在任何值。void, 无或者空类型。大部分编程语言支持void, 用做函数无返回值类型。最早ALGOL 68引入void类型。 void的特别使用 经典C缺乏void类型&#xff0c;函数可以不指定返回值&#xff0c;默认是整型int.…...

10/1 力扣 49.字母异位词分组

基本知识&#xff1a; 关于字符串的排序&#xff1a; 1.多个字符串排序 1.1使用python内置的sorted() 使用该函数后原对象并不发生变化 1.2若多个字符串使用列表进行存储&#xff0c;使用列表的sort()方法 使用该函数后原对象原地变化 2.对单个字符串里的字母进行排序 使…...

✨机器学习笔记(六)—— ReLU、多分类问题、Softmax、Adam、反向传播

Course2-Week2: https://github.com/kaieye/2022-Machine-Learning-Specialization/tree/main/Advanced%20Learning%20Algorithms/week2机器学习笔记&#xff08;六&#xff09; 1️⃣ReLU&#xff08;Rectified Linear Unit&#xff09;2️⃣多分类问题3️⃣Softmax4️⃣Adam5…...

Xshell7下载及服务器连接

一、Xshell-7.0.0164p、Xftp 7下载 1.1、文件下载 通过网盘分享的文件&#xff1a;xshell 链接: https://pan.baidu.com/s/1qc0CPv4Hkl19hI9tyvYZkQ 提取码: 5snq –来自百度网盘超级会员v2的分享 1.2、ip连接 下shell和xftp操作一样&#xff1a;找到文件—》新建—》名称随…...

SQL Server—的数据类型

SQL Server—的数据类型 在 SQL Server 数据库中&#xff0c;数据类型是定义数据模型的基础&#xff0c;它们决定了数据在数据库中的存储方式和格式。正确选择数据类型不仅可以优化存储空间&#xff0c;还能提高查询性能和数据完整性。 1文本类型 文本类型&#xff1a;字符数…...

WaterCloud:一套基于.NET 8.0 + LayUI的快速开发框架,完全开源免费!

前言 今天大姚给大家分享一套基于.NET 8.0 LayUI的快速开发框架&#xff0c;项目完全开源、免费&#xff08;MIT License&#xff09;且开箱即用&#xff1a;WaterCloud。 可完全实现二次开发让开发更多关注业务逻辑。既能快速提高开发效率&#xff0c;帮助公司节省人力成本&…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...

Java后端检查空条件查询

通过抛出运行异常&#xff1a;throw new RuntimeException("请输入查询条件&#xff01;");BranchWarehouseServiceImpl.java // 查询试剂交易&#xff08;入库/出库&#xff09;记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...