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

二分图(染色法与匈牙利算法)

二分图当且仅当一个图中不含奇数环

1.染色法

简单来说,将顶点分成两类,边只存在于不同类顶点之间,同类顶点之间没有边。

e.g.

如果判断一个图是不是二分图?

开始对任意一未染色的顶点染色。

判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色。

若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图,若颜色不同则继续判断。

bfs和dfs可以搞定!

 注意:如果有三个点另外成环,整个环是一个孤立环,其他都满足二分图,但是这个孤立不满足二分图,二分图的点不一定连通。所以要遍历每一个点。

1.dfs思路:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200010;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int n,m;
int color[N];
void add(int a, int b)//邻接表插入点和边
{e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}
bool dfs(int a,int c){color[a]=c;for(int i=h[a];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;
}
int main(){memset(h, -1, sizeof h);//初始化邻接表cin >> n >> m;for(int i = 1; i <= m; i++)//读入边{int a, b;cin >> a >> b;add(a, b), add(b, a);}for(int i=1;i<=n;i++){if(!color[i]){if(!dfs(i,1)){puts("No");return 0;}}}puts("Yes");return 0;
}

2.bfs思路:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=200010;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int n,m;
int color[N];queue<int> q;
void add(int a, int b)//邻接表插入点和边
{e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}
bool bfs(int a){color[a]=1;q.push(a);while(q.size()){auto t=q.front();q.pop();for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(!color[j]){color[j]=3-color[t];q.push(j);}else if(color[j]==color[t]) return false;}}return true;
}
int main(){memset(h, -1, sizeof h);//初始化邻接表cin >> n >> m;for(int i = 1; i <= m; i++)//读入边{int a, b;cin >> a >> b;add(a, b), add(b, a);}for(int i=1;i<=n;i++){if(!color[i]){if(!bfs(i)){puts("No");return 0;}}}puts("Yes");return 0;
}

2.匈牙利算法

要了解匈牙利算法必须先理解下面的概念:

匹配:在图论中,一个「匹配」是一个边的集合,其中任意两条边都没有公共顶点。

最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。

这篇文章把这个算法讲的很有意思: 

趣写算法系列之--匈牙利算法_匈牙利算法基本原理-CSDN博客 

简单来说就是:

遍历所有男生
让该男生考虑所有心动女生
如果当前女生单身,或者该女生的对象找了备胎,该女生就接受该男生
最坏时间复杂度 O(nm),和其它最大流问题一样,实际比较快

 

#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];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool find(int x){for(int i=h[x];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){st[j]=1;if(match[j]==0||find(match[j])){match[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);if (find(i)) res ++ ;}printf("%d\n", res);return 0;
}

在上述代码中,有一个令人费解的东西:就是st数组的作用,其实直白的理解:如果你每次不把st重新置为false,那剩下的人一看到前面的妹子st已经为true,不去让妹子的对象换掉这个妹子,直接就放弃了,会影响最后结果。

我们通过一个实际案例理解一下:

不难看出,st数组主要是在两个人连接了一个妹子的的时候才有用, 这个st的存在,让find在本次找的时候,原来的那个男生,不会再找这个妹子,只会找其他的。

还有一种理解:st的理解可以参考操作系统中锁的概念。假如说左边的是进程,右边的是资源。当进程i要访问资源j时,为了避免其他进程在此时访问资源j,需要对资源j加一个“锁”,即st[j] = true。当进程i访问完资源时,为了让后续其他进程也能访问资源,需要把锁解开,即memset(st, false, sizeof st)。

相关文章:

二分图(染色法与匈牙利算法)

二分图当且仅当一个图中不含奇数环 1.染色法 简单来说&#xff0c;将顶点分成两类&#xff0c;边只存在于不同类顶点之间&#xff0c;同类顶点之间没有边。 e.g. 如果判断一个图是不是二分图&#xff1f; 开始对任意一未染色的顶点染色。 判断其相邻的顶点中&#xff0c;若未…...

ReactFlow的ReactFlow实例事件传参undefined处理状态切换

1.问题 ReactFlow的ReactFlow实例有些事件我们在不同的状态下并不需要&#xff0c;而且有时候传参会出现其它渲染效果&#xff0c;比如只读状态下我们不想要拖拉拽onEdgesChange连线重连或删除的功能。 2.思路 事件名称类型默认值onEdgesChange(changes: EdgeChange[]) >…...

Dockerfile 和 Docker Compose

Dockerfile 和 Docker Compose 是 Docker 生态系统中两个重要的组成部分&#xff0c;它们分别服务于不同的目的&#xff0c;但共同协助开发者和运维人员高效地管理和部署容器化应用。 Dockerfile Dockerfile 是一个文本文件&#xff0c;包含了构建 Docker 镜像所需的一系列指…...

多个文件 import 的相同模块里的对象

多个文件 import 的相同模块里的对象&#xff0c;是否永远都是同一个对象&#xff1f; 在store的index.js中 import vue from ‘vue’ import Vuex from ‘vuex’ 并配置有关对象 然后再app.vue中配置vm 在不同的文件中 import一个vue对象&#xff0c;在任何情况下&#…...

面试经典150题——验证回文串

面试经典150题 day25 题目来源我的题解方法一 双指针方法二 双指针 空间优化 题目来源 力扣每日一题&#xff1b;题序&#xff1a;125 我的题解 方法一 双指针 首先去除掉字符串中的无用字符&#xff0c;并将英文字符转换为小写&#xff0c;然后使用双指针来判断是否是回文串…...

YOLOv8的训练、验证、预测及导出[目标检测实践篇]

这一部分内容主要介绍如何使用YOLOv8训练自己的数据集&#xff0c;并进行验证、预测及导出&#xff0c;采用代码和指令的两种方式&#xff0c;参考自官方文档&#xff1a;Detect - Ultralytics YOLOv8 Docs。实践篇不需要关注原理&#xff0c;只需要把流程跑通就行&#xff0c;…...

光伏远动通讯屏的组成

光伏远动通讯屏的组成 远动通讯屏主要用于电力系统数据采集与转发&#xff0c;远动通讯屏能够采集站内的各种数据&#xff0c;如模拟量、开关量和数字量等&#xff0c;并通过远动通讯规约将必要的数据上传至集控站或调度系统。这包括但不限于主变和输电线路的功率、电流、电压等…...

营销H5测试综述

H5页面是营销域最常见的一种运营形式&#xff0c;业务通过H5来提供服务&#xff0c;可以满足用户对于便捷、高效和低成本的需求。H5页面是业务直面用户的端点&#xff0c;其质量保证工作显得尤为重要。各业务的功能实现具有通用性&#xff0c;相应也有共性的测试方法&#xff0…...

【C++随记4】C++二进制位操作运算符

在C中&#xff0c;二进制位操作运算符允许你直接对整数类型的变量的位进行操作。这些运算符包括&#xff1a; 按位与&#xff08;Bitwise AND&#xff09;: & 按位或&#xff08;Bitwise OR&#xff09;: | 按位异或&#xff08;Bitwise XOR&#xff09;: ^ 按位取反&…...

风电厂数字孪生3D数据可视化交互展示构筑智慧化电厂管理体系

随着智慧电厂成为未来电力企业发展的必然趋势&#xff0c;深圳华锐视点紧跟时代步伐&#xff0c;引领技术革新&#xff0c;推出了能源3D可视化智慧管理系统。该系统以企业现有的数字化、信息化建设为基础&#xff0c;融合云平台、大数据、物联网、移动互联、机器人、VR虚拟现实…...

大模型市场爆发式增长,但生成式AI成功的关键是什么?

进入2024年&#xff0c;大模型市场正在爆发式增长。根据相关媒体的总结&#xff0c;2024年1-4 月被统计到的大模型相关中标金额已经达到2023年全部中标项目披露金额的77%左右&#xff1b;其中&#xff0c;从项目数量来看&#xff0c;应用类占63%、算力类占21%、大模型类占13%、…...

leetcode LCR088.使用最小花费爬楼梯

思路&#xff1a;DP 这道题相对来说比较基础&#xff0c;但是有时候容易出错的一点就是在dp递推的时候&#xff0c;由于我们的思路是从最后一步向着初始状态推的&#xff0c;所以在编写程序的时候也容易就直接推着走了。其实实际上我们倒着想只是为了推理&#xff0c;真正要递…...

【DevOps】怎么提升Elasticsearch 的搜索性能

一、怎么提升Elasticsearch 搜索性能 提升 Elasticsearch (ES) 的搜索性能可以从多个角度进行优化&#xff0c;包括硬件选择、配置调整、查询优化等。以下是一些具体的方法和建议&#xff1a; 1. 硬件优化 使用 SSDs&#xff1a; 使用固态硬盘&#xff08;SSD&#xff09;而…...

启动任何类型操作系统:不需要检索 ISO 文件 | 开源日报 No.243

netbootxyz/netboot.xyz Stars: 7.7k License: Apache-2.0 netboot.xyz 是一个方便的平台&#xff0c;可以不需要检索 ISO 文件就能启动任何类型操作系统或实用工具磁盘。它使用 iPXE 提供用户友好的 BIOS 菜单&#xff0c;让您轻松选择所需的操作系统以及特定版本或可引导标志…...

Linux——综合实验

要求 按照上面的架构部署一个简单的web节点所有的服务器使用DNS服务器作为自己的DNS服务器 就是/etc/reslov.conf 中nameserver的值必须是途中dns服务器的地址所有的数据库都是用mysql应用 nfs共享导出在客户端(web服务器上)使用autofs在自动挂载&#xff0c;或者写入/etc/fsta…...

oracle数据库用户名修改

在Oracle数据库中&#xff0c;修改用户名通常涉及一系列步骤。以下是修改Oracle数据库用户名的详细步骤&#xff1a; 修改前准备工作&#xff1a; 使用ssh工具以root身份连接服务器。 切换到oracle用户&#xff1a;su - oracle&#xff08;回车&#xff09; 使用sqlplus连接数…...

2024年开抖音小店需要多少钱?你真的知道吗?最新入驻条件及费用

大家好&#xff0c;我是电商花花。 现在仍然有很多想开抖店&#xff0c;想做抖音小店&#xff0c;但是很多人都不知道投资一家抖音小店需要多少钱&#xff0c;今天花花就给大家讲一下做一家抖音小店需要投入多少资金&#xff0c;以及具体投入到哪些方面。 我们就说一下个体店…...

Vue创建todolist

电子书 第三章&#xff1a; https://www.dedao.cn/ebook/reader?idV5R16yPmaYOMqGRAv82jkX4KDe175w7xRQ0rbx6pNgznl9VZPLJQyEBodb89mqoO 没有使用VUE CLI创建项目。 创建步骤&#xff1a; 1&#xff0c; 用Vite 创建项目 2&#xff0c; npm run dev 运行程序 参照之前的文…...

了解Ansible Playbook

在现代IT运维中&#xff0c;自动化部署成为了提高效率、降低错误率的重要手段之一。而Ansible作为一种强大的自动化工具&#xff0c;其Playbook机制为自动化部署提供了灵活、可扩展的解决方案。本文将深入介绍Ansible Playbook的概念、结构、语法和常见用法&#xff0c;帮助读者…...

nginx 负载均衡、反向代理实验

nginx 负载均衡、反向代理实验 实验目的 理解概念&#xff1a;明确反向代理和负载均衡的基本概念及其在网络架构中的作用。 掌握技能&#xff1a;学习如何配置Nginx以实现反向代理和负载均衡功能。 实践应用&#xff1a;通过实际操作&#xff0c;体验Nginx如何提升Web服务的可…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

论文阅读:Matting by Generation

今天介绍一篇关于 matting 抠图的文章&#xff0c;抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法&#xff0c;已经有很多的工作和这个任务相关。这两年 diffusion 模型很火&#xff0c;大家又开始用 diffusion 模型做各种 CV 任务了&am…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...