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

信息学奥赛一本通 1520:【 例 1】分离的路径 | 洛谷 P2860 [USACO06JAN]Redundant Paths G

【题目链接】

ybt 1520:【 例 1】分离的路径
洛谷 P2860 [USACO06JAN]Redundant Paths G

【题目考点】

1. 图论:割边(桥) 边双连通分量

【解题思路】

每个草场是一个顶点,草场之间的双向路是无向边,该图是无向图。建新的道路,就是添加边。
“每对草场之间已经有至少一条路径”,表示该图是连通图。
“同一对草场之间,可能已经有两条不同的道路”,表示图中可能有重边。
“使每一对草场之间都会至少有两条相互分离的路径”,而且“两条路径相互分离,是指两条路径没有一条重合的道路”,也就是希望最后图中任何两个顶点之间都有两条边不重复的路径,这样的图就是边双连通图。
求的是最少增加的路径的数目。
该题抽象后可以描述为:给定一个无向图,求最少添加几条边可以使该图变为边双连通图。

如果两顶点处于一个边双连通分量中,那么这两顶点之间就一定不需要添加边,因为两顶点之间已经存在两条边不重复的路径。因此只有两顶点在不同的边双连通分量中,才需要考虑是否需要在两顶点之间添加边。
这里可以考虑将图中每个边双连通分量变为一个顶点,也就是“缩点”,缩点后的图一定不存在双连通分量,是无环连通图,也就是树。

反证:如果缩点后存在环,那么环上多个顶点处于一个双连通分量中,在原图中该环连接的所有双连通分量应该同属于一个双连通分量,应该缩为一个点而不是多个点。

考虑要想使缩点后的树变为双连通图,需要添加最少多少条边。
树上任意两顶点连线后,就会形成一个环,该环就是一个双连通分量。
由于环上的顶点都是度为2的顶点,因此树上叶子结点,也就是度为1的顶点要想处于一个环上,必须在度为1的顶点上连接新的边,使该顶点度变为2。
因此每次添加一条边连接两个度为1的顶点,让这两个顶点在树上的路径加上新的边形成一个环。
每两个度为1的顶点需要添加一条边,如果剩下单独一个顶点,也需要在该顶点上增加一条到其它顶点的边。
如果叶子结点数量为 d d d,那么需要添加边的数量为 ⌈ d 2 ⌉ \lceil \frac{d}{2} \rceil 2d,也就是 d + 1 2 \frac{d+1}{2} 2d+1

【题解代码】

解法1:Tarjan算法直接求边双连通分量
#include <bits/stdc++.h>
using namespace std;
#define N 5005
int n, m, fa[N], ebc[N], en, deg[N];
vector<int> edge[N];
int dfn[N], low[N], ts;
stack<int> stk;
void tarjan(int u)
{int t, fromEdge = 0;//fromEdge:从fa[u]到u的边的数量 dfn[u] = low[u] = ++ts;stk.push(u);for(int v : edge[u]){if(dfn[v] == 0){fa[v] = u;tarjan(v);low[u] = min(low[u], low[v]);}else if(v != fa[u] || ++fromEdge > 1)//如果fromEdge==2,那么(u, fa[u])存在重边,更新low[u]后可以保证(u,fa[u])不是桥 low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){en++;do{t = stk.top();stk.pop();ebc[t] = en;}while(t != u);}
}
int main()
{int f, t, degOneCt = 0;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t;edge[f].push_back(t);edge[t].push_back(f);}for(int v = 1; v <= n; ++v)	if(dfn[v] == 0)tarjan(v);for(int u = 1; u <= n; ++u)for(int v : edge[u]) if(ebc[v] != ebc[u])deg[ebc[v]]++, deg[ebc[u]]++;for(int i = 1; i <= en; ++i)//<u, v>, <v, u>统计两次,顶点的度应该除以2 deg[i] /= 2;for(int i = 1; i <= en; ++i) if(deg[i] == 1)//统计度为1的双连通分量的数量 degOneCt++;cout << (degOneCt+1)/2;return 0;
}
解法2:Tarjan算法先求桥,再求双连通分量
#include <bits/stdc++.h>
using namespace std;
#define N 5005
int n, m, fa[N], ebc[N], en, deg[N];
vector<int> edge[N];
int dfn[N], low[N], ts;
bool bridge[N], vis[N];//bridge[i]:(i, fa[i])是否是桥
bool isBridge(int u, int v)
{return fa[u] == v && bridge[u] || fa[v] == u && bridge[v];
}
void tarjan(int u)
{int t, fromEdge = 0;//fromEdge:从fa[u]到u的边的数量 dfn[u] = low[u] = ++ts;for(int v : edge[u]){if(dfn[v] == 0){fa[v] = u;tarjan(v);low[u] = min(low[u], low[v]);if(dfn[u] < low[v])bridge[v] = true;//(u,v)是桥 }else if(v != fa[u] || ++fromEdge > 1)//如果fromEdge==2,那么(u, fa[u])存在重边,更新low[u]后可以保证(u,fa[u])不是桥 low[u] = min(low[u], dfn[v]);}
}
void dfs(int u)
{vis[u] = true;ebc[u] = en;for(int v : edge[u]) if(!vis[v] && !isBridge(u, v))dfs(v);
}
int main()
{int f, t, degOneCt = 0;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t;edge[f].push_back(t);edge[t].push_back(f);}for(int v = 1; v <= n; ++v)	if(dfn[v] == 0)tarjan(v);for(int v = 1; v <= n; ++v) if(!vis[v]){++en;dfs(v);	}for(int u = 1; u <= n; ++u)for(int v : edge[u]) if(ebc[v] != ebc[u])deg[ebc[v]]++, deg[ebc[u]]++;for(int i = 1; i <= en; ++i)//<u, v>, <v, u>统计两次,顶点的度应该除以2 deg[i] /= 2;for(int i = 1; i <= en; ++i) if(deg[i] == 1)//统计度为1的双连通分量的数量 degOneCt++;cout << (degOneCt+1)/2;return 0;
}

相关文章:

信息学奥赛一本通 1520:【 例 1】分离的路径 | 洛谷 P2860 [USACO06JAN]Redundant Paths G

【题目链接】 ybt 1520&#xff1a;【 例 1】分离的路径 洛谷 P2860 [USACO06JAN]Redundant Paths G 【题目考点】 1. 图论&#xff1a;割边&#xff08;桥&#xff09; 边双连通分量 【解题思路】 每个草场是一个顶点&#xff0c;草场之间的双向路是无向边&#xff0c;该…...

架构师面试(六):熔断和降级

问题 在千万日活的电商系统中&#xff0c;商品列表页服务通过 RPC 调用广告服务&#xff1b;经过统计发现&#xff0c;在最近10秒的时间里&#xff0c;商品列表页服务在对广告服务的调用中有 98% 的调用是超时的&#xff1b; 针对这个场景&#xff0c;下面哪几项的说法是正确的…...

使用 DeepSeek 生成流程图、甘特图与思维导图:结合 Typora 和 XMind 的高效工作流

在现代工作与学习中&#xff0c;可视化工具如流程图、甘特图和思维导图能够极大地提升信息整理与表达的效率。本文将详细介绍如何使用 DeepSeek 生成 Mermaid 文本&#xff0c;结合 Typora 快速生成流程图和甘特图&#xff0c;并通过 Markdown 格式生成思维导图&#xff0c;最终…...

粘贴到Word里的图片显示不全

粘贴到Word里的图片显示不全&#xff0c;可从Word设置、图片本身、软件与系统等方面着手解决&#xff0c;具体方法如下&#xff1a; Word软件设置 经实践发现&#xff0c;图片在word行距的行距出现问题&#xff0c;可以按照如下调整行距进行处理 修改段落行距&#xff1a; 选…...

【C语言】结构体内存对齐问题

1.结构体内存对齐 我们已经基本掌握了结构体的使用了。那我们现在必须得知道结构体在内存中是如何存储的&#xff1f;内存是如何分配的&#xff1f;所以我们得知道如何计算结构体的大小&#xff1f;这就引出了我们今天所要探讨的内容&#xff1a;结构体内存对齐。 1.1 对齐规…...

【蓝桥杯单片机】第十三届省赛第二场

一、真题 二、模块构建 1.编写初始化函数(init.c) void Cls_Peripheral(void); 关闭led led对应的锁存器由Y4C控制关闭蜂鸣器和继电器 2.编写LED函数&#xff08;led.c&#xff09; void Led_Disp(unsigned char ucLed); 将ucLed取反的值赋给P0 开启锁存器 关闭锁存…...

类与对象(5)

上一章是类与对象&#xff08;4&#xff09;-CSDN博客 深入了构造函数和静态成员&#xff0c;大概讲解了类型转换 最后一章最后一章 友元 在 C 中&#xff0c;友元提供了一种突破类的访问控制&#xff08;封装&#xff09;的方式。通过友元&#xff0c;外部的函数或类可以访…...

AI知识架构之数据采集

数据采集 数据格式: 结构化数据:以固定格式和结构存储,如数据库中的表以及 Excel 表格,易于查询和分析。半结构化数据:有一定结构但不如结构化数据严格,XML 常用于数据交换,JSON 在 Web 应用中广泛用于数据传输和存储。非结构化数据:无预定义结构,文本、图像、音频和视…...

细说STM32F407单片机2个ADC使用DMA同步采集各自的1个输入通道的方法

目录 一、示例说明 二、工程配置 1、RCC、DEBUG、CodeGenerator 2、USART6 3、TIM3 &#xff08;1&#xff09;Mode &#xff08;2&#xff09;参数设置 &#xff08;3&#xff09; TRGO &#xff08;4&#xff09;ADC1_IN0 1&#xff09;ADCs_Common_Settings 2&a…...

C# 将非托管Dll嵌入exe中(一种实现方法)

一、环境准备 电脑系统:Windows 10 专业版 20H2 IDE:Microsoft Visual Studio Professional 2022 (64 位) - Current 版本 17.11.4 其他: 二、测试目的 将基于C++创建DLL库,封装到C#生成的exe中。 一般C++创建的库,在C#中使用,都是采用DllImport导入的,且要求库处…...

完美解决:.vmx 配置文件是由 VMware 产品创建,但该产品与此版 VMware Workstation 不兼容

参考文章&#xff1a;该产品与此版 VMware Workstation 不兼容&#xff0c;因此无法使用 问题描述 当尝试使用 VMware Workstation 打开别人的虚拟机时&#xff0c;可能会遇到以下报错&#xff1a; 此问题常见于以下场景&#xff1a; 从其他 VMware 版本&#xff08;如 ESX…...

使用大语言模型对接OA系统,实现会议室预定功能

随着人工智能技术的不断进步&#xff0c;越来越多的企业开始借助 AI 助手来提高工作效率&#xff0c;尤其是在日常事务的自动化处理中。比如&#xff0c;在许多公司里&#xff0c;会议室的预定是一个常见且频繁的需求&#xff0c;通常需要员工手动检查空闲时间并做出选择。而通…...

Ryu控制器:L2交换功能实现案例

基于 Ryu控制器 在 VM1--OVS--VM2 的简单拓扑中实现流量自动下发&#xff08;流表动态安装&#xff09;的完整案例。通过该案例&#xff0c;当VM1与VM2首次通信时&#xff0c;Ryu控制器会动态学习路径并下发流表&#xff0c;后续流量将直接由交换机转发&#xff0c;无需控制器介…...

动手学深度学习2025.2.23-预备知识之-线性代数

3.线性代数 &#xff08;1&#xff09;向量维数和张量维数的区别&#xff1a; (2)普通矩阵乘法&#xff1a; 要求左矩阵的列数等于右矩阵的行数 import torch ​ # 创建两个矩阵 A torch.tensor([[1, 2], [3, 4]], dtypetorch.float32) B torch.tensor([[5, 6], [7, 8]], d…...

登录-07.JWT令牌-登录后下发令牌

一.思路 我们首先完成令牌生成。 在响应数据这一块 该响应数据是一个标准的Result结构&#xff0c;其中"data"的值就是一个JWT令牌。因此我们只需要将生成的JWT令牌封装在Result当中然后返回给前端即可。 备注是给前端看的&#xff0c;不用管。以后我们做校验时&…...

机器学习实战(7):聚类算法——发现数据中的隐藏模式

第7集&#xff1a;聚类算法——发现数据中的隐藏模式 在机器学习中&#xff0c;聚类&#xff08;Clustering&#xff09; 是一种无监督学习方法&#xff0c;用于发现数据中的隐藏模式或分组。与分类任务不同&#xff0c;聚类不需要标签&#xff0c;而是根据数据的相似性将其划…...

【数据序列化协议】Protocol Buffers

一、为什么需要序列化&#xff1f; 数据跨平台/语言交互&#xff1a; 不同编程语言&#xff08;如 Java、Python、Go&#xff09;的数据结构不兼容&#xff0c;序列化提供统一的数据表示。例如&#xff1a;Java 的 HashMap 和 Python 的 dict 需转换为通用格式&#xff08;如 …...

基于 Python 的电影市场预测分析系统设计与实现(源码 + 文档)

大家好&#xff0c;今天要和大家聊的是一款基于 Python 的“电影市场预测分析”系统的设计与实现。项目源码以及部署相关事宜请联系我&#xff0c;文末附上联系方式。 项目简介 基于 Python 的“电影市场预测分析”系统主要面向以下用户角色&#xff1a;电影制片方、电影发行…...

计算机三级网络技术知识汇总【6】

第六章 交换机及其配置 1. 交换机基础 1.1 基本概念 局域网交换机是一种基于 MAC 地址识别&#xff0c;完成转发数据帧功能的一种网络连接设备。 工作在数据链路层&#xff0c;根据进入端口数据帧中的 MAC 地址进行数据帧的过滤、转发&#xff08;也是交换机的工作原理&…...

2025教育与科研领域实战全解析:DeepSeek赋能细分场景深度指南(附全流程案例与资源)

🚀 2025教育与科研领域实战全解析:DeepSeek赋能细分场景深度指南(附全流程案例与资源)🚀 📚 目录 DeepSeek在教育与科研中的核心价值教学场景应用:从备课到课堂管理的全流程革新科研场景应用:从数据分析到论文写作的智能跃迁师生协同创新:AI赋能的个性化学习与科研…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...