【图论】二分图
二分图,即可以将图中的所有顶点分层两个点集,每个点集内部没有边
判定图为二分图的充要条件:有向连通图不含奇数环
1、染色法
可以解决二分图判断的问题
步骤与基本思路
遍历图中每一个点,若该点未被染色,则遍历该点所相邻的点,相邻的点中未被染色的进行染色操作,已被染色的判断颜色是否合法,合法继续遍历,不合法退出
染色法板子
bool flag = true;
for (int i = 1; i <= n; i ++ )
{if (!color[i]) // 未被染色则开始遍历{if (!dfs(i, 1)){flag = false;break;}}
}bool dfs(int u, int c)
{color[u] = c; // 对该点进行染色for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (!color[j]) // 未被染色的点进行染色{if (!dfs(j, 3 - c)) return false;}else if (color[j] == c) return false; // 已染色的点判断是否合法}return true;
}
2、匈牙利算法
可以解决最大匹配数的问题,也就是二分图的两个点集可以连多少条一一对应的边
步骤与基本思路
(1)遍历第一个点集的所有点,每个点遍历之前要记得把第二个点集的状态清空
(2)依次遍历这些点相邻的点,若该点未被遍历过,则判断该点是否满足未与前面的点匹配过或前面与它匹配的点有其他的匹配方案,若满足任意条件则让现在的两点匹配,不满足则说明当前第一个点集的这个点没有匹配对象
匈牙利算法板子
for (int i = 1; i <= n1; i ++ )
{memset(st, false, sizeof st); // 清空第二个点集的状态if (find(i)) res ++ ;
}bool find(int x)
{for (int i = h[x]; i != -1; i = ne[i]){int j = e[i];if (!st[j]) // 若该点未被遍历过{st[j] = true;// 该点是否满足 未被匹配过 or 匹配的第一个点集的点有其他成功匹配方案if (match[j] == 0 || find(match[j])){match[j] = x; // 匹配现在的这两点return true;}}}return false;
}
相关文章:
【图论】二分图
二分图,即可以将图中的所有顶点分层两个点集,每个点集内部没有边 判定图为二分图的充要条件:有向连通图不含奇数环 1、染色法 可以解决二分图判断的问题 步骤与基本思路 遍历图中每一个点,若该点未被染色,则遍历该…...
数据结构——(一)绪论
👉数据元素整体思维导图 欢迎补充 一、基本概念❤️ 1.1基本术语⭐️ (1)数据 客观事务属性的数字、字符。 (2)数据元素 数据元素是数据的基本单位,一个数据元素可由若干数据项组成,数据项是…...
[ 华为云 ] 云计算中Region、VPC、AZ 是什么,他们又是什么关系,应该如何抉择
前几天看到一个问答帖,我回答完了才发现这个帖子居然是去年的也没人回复,其中他问了一些华为云的问题,对于其中的一些概念,这里来总结讲解一下,希望对学习华为云的小伙伴有所帮助。 文章目录 区域(Region&a…...
表单验证:输入的字符串以回车分隔并验证是否有
公司项目开发时,有一个需求,需要对输入的字符串按回车分隔并验证是否有重复项,效果如下: 表单代码: <el-form-item label"IP地址条目:" prop"ipAddressEntry"><el-inputtype&…...
智能财务分析-亿发财务报表管理系统,赋能中小企业财务数字化转型
对于许多中小企业来说,企业重要部门往往是财务和业务部门。业务负责创收,财务负责控制成本,降低税收风险。但因管理机制和公司运行制度的原因,中小企业往往面临着业务与财务割裂的问题,财务数据不清晰,无法…...
图为科技T501赋能工业机器人 革新传统工业流程
工业机器人已成为一个国家制造技术与科技水平的重要衡量标准,在2019年,中国工业机器人的组装量与产量均位居了全球首位。 当前,工业机器人被广泛用于电子、物流、化工等多个领域之中,是一种通过电子科技和机械关节制作出来的智能机…...
安全狗深度参与编写的《云原生安全配置基线规范》正式发布!
7月25日,由中国信息通信研究院、中国通信标准化协会主办的2023可信云大会在北京顺利开幕。 作为国内云原生安全领导厂商,安全狗受邀出席此次活动。 厦门服云信息科技有限公司(品牌名:安全狗)成立于2013年,…...
如何在3ds max中创建可用于真人场景的巨型机器人:第 2 部分
推荐: NSDT场景编辑器助你快速搭建可二次开发的3D应用场景 1. 创建主体 步骤 1 打开 3ds Max。选择机器人头部后,二次单击鼠标并选择隐藏未选中。机器人的其他部分 除了头部之外,将被隐藏。 打开 3ds Max 步骤 2 在人脸选择模式下&#x…...
Vue中TodoList案例_编辑
nextTick: MyItem.vue 加一个编辑按钮,input框:blur失去焦点时触发事件handleBlur,ref获取真实dom: <inputtype"text"v-show"todo.isEdit":value"todo.title"blur"handleBlur(todo,$even…...
什么是Redis?
什么是Redis 什么是Redis一、特性1. 支持多种数据结构2. 读/写速度快,性能高。3. 支持持久化。4. 实现高可用主从复制,主节点做数据副本。5. 实现分布式集群和高可用。 二、基本数据类型string(字符串)list(双向链表)set(集合)zse…...
深入浅出理解vue2/vue3响应式原理
一、简介 当谈论Vue 2和Vue 3的响应式原理时,我们主要关注的是其数据双向绑定的机制。数据双向绑定是指当数据发生变化时,视图会自动更新;反之,当视图发生变化时,数据也会相应地更新。这种特性让我们在前端开发中更加…...
ssh连接服务器配置
平常每次都是 ssh root111.111.111.111 然后再输入密码 很事麻烦 总结 首先本地生成密钥和公钥 ssh-keygen -t rsa -C "XXX" ~/.ssh id_rsa.pub 将公钥加入远程服务器中的authorized_keys中 用户可以手动编辑该文件,把公钥粘贴进去,也可…...
el-table 表头设置渐变色
<el-table :data"tableData" stripe><el-table-column prop"name" label"测试" align"left"></el-table-column><el-table-column prop"code" label"测试1" align"left"></…...
GB/T 25000.51解读——软件产品的易用性怎么测?
GB/T 25000.51-2016《软件产品质量要求和测试细则》是申请软件检测CNAS认可一定会用到的一部国家标准。在前面的文章中,我们为大家整体介绍了GB/T 25000.51-2016《软件产品质量要求和测试细则》国家标准的结构和所涵盖的内容以及对软件产品的八大质量特性中的功能性…...
408复试day2(7大排序算法)
数据结构 7大排序算法总结: 首先排序分为内排序和外排序: 内排序是指待排序的记录放置在内存,而外排序是指排序的过程中需要对内存进行访问。其中稳定的排序有“插冒归”,即插入排序、冒泡排序、归并排序。 1.冒泡排序 算法原理&a…...
Vue消息订阅与发布
引入第三方库pubsub.js: npm i pubsub-js Student.vue import pubsub from pubsub-jsmethods:{sendStudentName(){// this.$bus.$emit(hello,this.name)pubsub.publish(hello,666)}}, School.vue import pubsub from pubsub-jsmounted() {// console.log("school&quo…...
MySQL学习笔记 ------ 分组查询
#进阶5:分组查询 /* 语法: select 分组函数,列(要求出现在group by的后面) from 表 【where 筛选条件】 group by 分组的列表 【order by 排序的字段】; 注意:查询列表必须特殊,要求是分组函…...
Matlab 点云平面特征提取
文章目录 一、简介二、实现代码2.1基于k个邻近点2.2基于邻近半径参考资料一、简介 点云中存在这各种各样的几何特征,这里基于每个点的邻域协方差来获取该点的所具有的基础几何特征(如下图所示),这样的做法虽然不能很好的提取出点云中的各个部分,但却是可以作为一种数据预处…...
vite的介绍
Vite(法语意为 "快速的",发音 /vit/,发音同 "veet")是一种新型前端构建工具 优势 💡 极速的服务启动,使用原生 ESM 文件,无需打包 ⚡️ 轻量快速的热重载,始终极快的模块…...
裁员 10%,暴跌 14%,这家 IT 独角兽正在被抛弃!
流量一跌再跌,Stack Overflow 简直被狠狠地上了一课! 3 月份 Stack Overflow 的流量下降了近 14%。该公司的 CEO 压力空前,甚至昨天决定裁员 10%! 平均每月下降6%,上月直接跌了近14% 开发人员越来越多地从 AI 聊天机器…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
