图论:合适的环
4979. 合适的环 - AcWing题库
给定一个 n 个点 m 条边的无向图。
图中不含重边和自环。
请你在图中选出一个由三个点组成的环。
设图中一共有 x 条边满足:不在选择的环内,且与选择的环内某个点相连。
我们希望通过合理选环,使得 x 的值尽可能小。
请你输出 x 的最小可能值。
输入格式
第一行包含两个整数 n,m。
接下来 m 行,每行包含两个整数 a,b,表示点 a和点 b 之间存在一条无向边。
输出格式
如果存在满足条件的环,则输出 x 的最小可能值。
否则,输出
-1。数据范围
前 33 个测试点满足 3≤n≤10,0≤m≤10。
所有测试点满足 3≤n≤4000,0≤m≤4000,1≤a,b≤n,a≠。输入样例1:
5 6 1 2 1 3 2 3 2 4 3 4 4 5输出样例1:
2样例1解释
给定图中,由三个点组成的环一共有两个,分别为点 1,2,3 组成的环以及点 2,3,4 组成的环。
对于点 1,2,3 组成的环,我们逐个分析每条边是否满足:不在环内,且与环内的某个点相连。
- 边 (1,2) 在环内。
- 边 (1,3 在环内。
- 边 (2,3)在环内。
- 边 (2,4)不在环内,且与点 2 相连。
- 边 (3,4)不在环内,且与点 3 相连。
- 边 (4,5)不在环内,但是与点 1,2,3 均不相连。
因此,如果选择点 1,2,3组成的环,则 x 的值为 2。
对于点 2,3,4 组成的环,我们逐个分析每条边是否满足:不在环内,且与环内的某个点相连。
- 边 (1,2) 不在环内,且与点 2 相连。
- 边 (1,3)不在环内,且与点 3 相连。
- 边 (2,3)在环内。
- 边 (2,4) 在环内。
- 边 (3,4) 在环内。
- 边 (4,5) 不在环内,且与点 4 相连。
因此,如果选择点 2,3,4组成的环,则 x 的值为 3。
综上,x 的最小可能值为 2。
输入样例2:
7 4 2 1 3 6 5 1 1 7输出样例2:
-1
图论问题,x 的表示选取的三个点各自和其他点连接成的线的数量之和(每个点排除共同形成环的另外两个点), 通过二维数组 arr[i][j]存储点,表示点 i 和点 j 之间存在一条线,结构体 s[i]{a,b} 存储线表示 第 i 条线由点 a 和 点 b 相连,mp[i] 存储第 i 个点和几个点相连, 根据题意,外循环遍历线1-m,可通过 s 得到连接线的两个点 a,b,内循环遍历第三个点 c,通过 arr 判断三个点之间是否都存在线,形成环,然后通过 mp 得到 x,因为 mp 存储的点 i 连接的其他所有点数量,但 x 求的是形成环的三个点分别排除与另外两点之间的线的情况,所以三个点每个点排除两条,三个点排除 6 条,一共就是 6 条,就是 -6.
AC code:
#include<bits/stdc++.h> using namespace std; int arr[4010][4010]; int n, m; struct s {int a, b; } s[4010]; unordered_map<int, int> mp; int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;s[i] = {a, b};arr[a][b]++;arr[b][a]++;mp[a]++, mp[b]++;}int ans = 2e9;for (int i = 1; i <= m; i++) {int a = s[i].a, b = s[i].b; // cout << a << " " << b<<endl;for (int c = 1; c <= n; c++) {if (arr[a][c] && arr[b][c]) {int res = mp[a] + mp[b] + mp[c] - 6;ans = min(res, ans);}}}if (ans != 2e9) {cout << ans;} else cout << -1;}
相关文章:
图论:合适的环
4979. 合适的环 - AcWing题库 给定一个 n 个点 m 条边的无向图。 图中不含重边和自环。 请你在图中选出一个由三个点组成的环。 设图中一共有 x 条边满足:不在选择的环内,且与选择的环内某个点相连。 我们希望通过合理选环,使得 x 的值尽可能…...
【数据分享】1929-2023年全球站点的逐月平均降水量(Shp\Excel\免费获取)
气象数据是在各项研究中都经常使用的数据,气象指标包括气温、风速、降水、湿度等指标,说到常用的降水数据,最详细的降水数据是具体到气象监测站点的降水数据! 有关气象指标的监测站点数据,之前我们分享过1929-2023年全…...
React+Antd实现省、市区级联下拉多选组件(支持只选省不选市)
1、效果 是你要的效果,咱们继续往下看,搜索面板实现省市区下拉,原本有antd的Cascader组件,但是级联组件必须选到子节点,不能只选省,满足不了页面的需求 2、环境准备 1、react18 2、antd 4 3、功能实现 …...
CentOS镜像如何下载?在VMware中如何安装?
一、问题 CentOS镜像如何下载?在VMware中如何安装? 二、解决 1、CentOS镜像的下载 (1)官方网站 The CentOS Project (2)官方中文官网 CentOS 中文 官网 (3)选择CentOS Linux…...
计算机科学导论(4)DMA传输原理
文章目录 DMA的工作原理DMA的优势DMA的类型DMA的应用 DMA(Direct Memory Access)直接内存访问是一种允许某些硬件子系统在不通过中央处理单元(CPU)的情况下,直接从内存读取或向内存写入数据的技术。这种方式可以显著提…...
select、poll和epoll的区别
文章目录 概要一、多路复用I/O模型的诞生1.1 多线程或进程方式1.2 通过数组,链表等方式保存socket fd,不断轮询 二、select三、poll四、epoll五、小结六、参考 概要 在Unix五种I/O模型一文中,提到了I/O多路复用模型,其在Linux下有…...
gpt今日最新新闻:gpts的广泛应用
最近,OpenAI给ChatGPT带来了一个备受期待的更新——“GPT提及(mentions)”功能。这项创新不仅增强了ChatGPT的实用性,也为AI在日常业务中的运用开辟了新路径。在本文中,我将分享我对这项新功能的初步体验,并…...
【进入游戏行业选游戏特效还是技术美术?】
进入游戏行业选游戏特效还是技术美术? 游戏行业正处于蓬勃发展的黄金时期,科技的进步推动了游戏技术和视觉艺术的飞速革新。在这个创意和技术挑战交织的领域里,游戏特效和技术美术岗位成为了许多人追求的职业目标。 这两个岗位虽然紧密关联…...
(delphi11最新学习资料) Object Pascal 学习笔记---第4章第2.3节(常量参数)
4.2.3 常量参数 作为引用参数的替代,您可以使用const参数。由于您无法在例程内为const参数赋予新值,因此编译器可以优化参数传递。编译器可以选择与引用参数相似的方法(或者在C术语中是const引用),但行为类似于值参…...
事件在状态流程图中的工作方式
什么是事件? 事件是一个Stateflow对象,它可以触发以下对象中一个动作: Simulink触发子系统 Simulink函数调用子系统 状态流程图 何时使用事件 当你想: 激活Simulink触发的子系统 激活Simulink函数调用子系统 在状态流程图…...
幻兽帕鲁能在Mac上运行吗?幻兽帕鲁Palworld新手攻略
幻兽帕鲁能在Mac上运行吗? 《幻兽帕鲁》目前还未正式登陆Mac平台,不过通过一些方法是可以让游戏在该平台运行的。 虽然游戏不能在最高配置下运行,但如果你安装了CrossOver这个软件,就可以玩了。这是为Mac、Linux和ChromeOS等设计…...
elementPlus实现动态表格单元格合并span-method方法总结
最近在做PC端需求的时候,需要把首列中相邻的同名称单元格合并。 我看了一下elementPlus官网中的table表格,span-method可以实现单元格合并。 我们先看一下官网的例子: 合并行或列 多行或多列共用一个数据时,可以合并行或列。 …...
视频上传 - 断点续传那点事
在上一篇文章中,我们讲解了分片上传的实现方式。在讲解断点续传之前,我要把上篇文章中留下的问题讲解一下。读过上一篇文章的小伙伴们都知道,对于分片上传来说,它的传输方式分为2种,一种是按顺序传输,一种是…...
Scala 和 Java在继承机制方面的区别
Scala 和 Java 都是面向对象编程语言,都支持类的继承机制。然而,尽管两者在基础概念上有很多相似之处,但在具体的实现和语法上,Scala 的继承机制有其独特之处。以下是 Scala 和 Java 在继承方面的一些主要区别: 多重继…...
spark sql上线前的调试工作实现
背景 每个公司应该都有大数据的平台的吧,平台的作用就是可以在上面执行各种spark sql以及定时任务,不过一般来说,由于这些spark sql的上线不经过测试,所以可能会影响到生产的数据,这种情况下大数据平台提供一个上线前…...
java -jar启动SpringBoot项目时配置文件加载位置与优先级
服务部署启动时,我们经常需要指定配置文件启动. 一般有四种,优先级如下 spring.config.location > spring.profiles.active > spring.config.additional-location > 默认的 application.yml 1.spring.config.location 外部配置文件优先级最高 一般配置文件在服务…...
每日一题 力扣LCP30.魔塔游戏
题目描述: 小扣当前位于魔塔游戏第一层,共有 N 个房间,编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums,其中正数表示道具补血数值,即血量增加对应数值;负数表示怪物造成伤害值&#x…...
iPhone搞机记录
-iPhone 8 或以上 设备进入DFU模式的方法: (适用:iPhone 8/8 Plus、iPhone X 系列、iPad Pro3 (11-inch)/(12.9-inch)) 1.保持设备处于开机或恢复模式下,插入数据线。 2.按一次设备的“音量加键”松开、再按一次“音量…...
Linux中共享内存(mmap函数的使用)
内存映射的基本使用 内存映射 概念: 使一个磁盘文件与内存中的一个缓冲区相映射,进程可以像访问普通内存一样对文件进行访问,不必再调用read,write。 mmap()的优点: 实现了用户空间和内核空间的高效交互方式 优化前:优…...
Golang与Erlang有什么差异
Golang和Erlang是两种备受关注的编程语言,它们各自具有独特的特点和优势。下面我将简单的探讨一下Golang和Erlang之间的差异,并且分析它们在并发模型、运行环境、函数式编程和领域特性等多个方面的不同之处。 并发模型 Golang使用goroutines和channels…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
