「清新题精讲」Skiers
更好的阅读体验
Skiers
Description
给定 n n n 个点的有向无环平面图,求最少多少条从 1 1 1 到 n n n 的路径能覆盖原图的所有边?
1 ≤ n ≤ 5 × 1 0 3 1\le n\le 5\times10^3 1≤n≤5×103
Solution
考虑从 1 1 1 到 n n n 的路径其实是边的链覆盖,那么最小链覆盖即为求解的答案。通过 Dilworth 定理可知,最小链覆盖等于最大反链,从而问题转化为求最大反链(两两无法到达的边的集合)。
例如:图示的有向无环平面图, 1 1 1 号点为起点, 7 7 7 号点为汇点。最大反链是 3 , 4 , 5 , 8 3,4,5,8 3,4,5,8 边构成的集合(注意集合不唯一),不难发现原图的答案就是 4 4 4。
考虑如何求解最大反链,可以将平面图转化为对偶图,则最大反链即为对偶图的最长路。
如图,给出了原图的对偶图的最长路,注意这里多开了虚拟起点和汇点。
那么,怎么求最长路呢,这里给出一种简单又迅速的做法,从起点开始 DFS,如果遍历到 1 1 1 个点之前已经遍历过了,那么说明多出了一条对偶图的边。
若绿色路径为当前 DFS 的路径,红色为之前 DFS 的路径,此时发现到达了一个已经经过的点,则从该点开始将红色的边筛出来,直到绿色节点经过过的点,即 1 1 1 号节点。用红色边最长路 + 1 +1 +1 再去更新绿色边的最长路即可。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int N = 5e3 + 10, M = 3 * N;int n;
int h[N], e[M], ne[M], idx;
int st[N], dp[M];
PII lst[N];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], dp[idx] = 1, h[a] = idx ++;
}
void dfs(int u) {st[u] = 1;for (int i = h[u]; ~i; i = ne[i]) {int v = e[i];if (st[v] == 0) lst[v] = {u, i}, dfs(v);else {int res = 0, tmp = u;while (st[v] == -1) res = max(res, dp[lst[v].se] + 1), v = lst[v].fi;dp[i] = res;while (tmp != v) dp[lst[tmp].se] = res, tmp = lst[tmp].fi;lst[e[i]] = {u, i};}}st[u] = -1;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin >> n;memset(h, -1, sizeof h);int k, x;for (int i = 1; i < n; i ++) {cin >> k;for (int j = 1; j <= k; j ++)cin >> x, add(i, x);}dfs(1);int res = 0;for (int i = 0; i < idx; i ++)res = max(res, dp[i]);cout << res << endl;return 0;
}
相关文章:
「清新题精讲」Skiers
更好的阅读体验 Skiers Description 给定 n n n 个点的有向无环平面图,求最少多少条从 1 1 1 到 n n n 的路径能覆盖原图的所有边? 1 ≤ n ≤ 5 1 0 3 1\le n\le 5\times10^3 1≤n≤5103 Solution 考虑从 1 1 1 到 n n n 的路径其实是边的链覆…...
Transformer详解(8)-基于transformer的英文到中文翻译模型
1、数据使用TED,数据清洗 WIT是“转录和翻译演讲网络清单”的缩写,是 TED 演讲多语言转录的现成版本,可用于研究目的。 2、英文中文翻译模型搭建 3、模型训练 4、模型推理...
算法的时间复杂度(详解)
前言: 算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为 输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果 一、算法效率 1.1 如何衡量一个算法的好坏 如何衡…...
Flutter 中的 NestedScrollViewViewport 小部件:全面指南
Flutter 中的 NestedScrollViewViewport 小部件:全面指南 Flutter 是一个功能丰富的 UI 工具集,它提供了多种布局和控件来帮助开发者构建美观且功能强大的应用。在 Flutter 的滚动控件中,NestedScrollView 是一个特别的存在,它允…...
断开自定义模块与自定义库的链接
断开自定义模块与自定义库的链接 1、断开模块与库的链接 1、断开模块与库的链接 如果摸个库文件添加到模型中,无法“Disable Link”时,可以使用save_system命令进行断开到模型中用户定义的库模块的链接; 参考链接: 传送门 save…...
粉丝问,有没有UI的统计页面,安排!
移动应用的数据统计页面具有以下几个重要作用: 监控业务指标:数据统计页面可以帮助用户监控关键业务指标和数据,例如用户活跃度、销售额、转化率等。通过实时更新和可视化呈现数据,用户可以及时了解业务的整体状况和趋势。分析用…...
Nginx R31 doc-17-debugging 调试
前言 大家好,我是老马。很高兴遇到你。 我们为 java 开发者实现了 java 版本的 nginx https://github.com/houbb/nginx4j 如果你想知道 servlet 如何处理的,可以参考我的另一个项目: 手写从零实现简易版 tomcat minicat 手写 nginx 系列 …...
python -【一】基础语法
python 基础语法 一. 基础数据类型 常用的 6 种数据类型 类型描述说明数字(Number)int,float,complex(复数),bool复数:4 3j,j 表示复数字符串(String)文本࿱…...
数据结构 | 详解二叉树——堆与堆排序
🥝堆 堆总是一棵完全二叉树。 大堆:父节点总是大于子节点。 小堆:父节点总是小于子节点。 注意:1.同一个节点下的两个子节点并无要求先后顺序。 2.堆可以是无序的。 🍉堆的实现 🌴深度剖析 1.父节点和子…...
vb.net,C#强制结束进程,“优雅”的退出方式
在VB.NET中,Application.Exit()和Environment.Exit(0)都用于结束程序,但它们的使用场景和背后的逻辑略有不同。 **Application.Exit()**: Application.Exit()通常用于Windows Forms应用程序中。当调用Application.Exit()时,它会触…...
牛客热题:数据流中的中位数
📟作者主页:慢热的陕西人 🌴专栏链接:力扣刷题日记 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 文章目录 牛客热题:数据流中的中位数题目链接方法一…...
JavaScript-JavaWeb
目录 什么是JavaScript? js引入方式 js基础语法 书写语法 变量 数据据类型 运算符 类型转换 流程语句 js函数 js对象 1.Array 2.String 3.JSON js事件监听 什么是JavaScript? ● JavaScript(简称:JS)是一门跨平台、面向对象的脚本语言。是用来控制网页行为的,它能…...
vue组件通讯$parent和$children获取单签组件的⽗组件和当前组件的⼦组件的例子
在 Vue 中,$parent 和 $children 是实例属性,允许你访问组件的父组件和子组件。但是,请注意,这些属性主要用于在开发过程中进行调试和临时访问,并不推荐在正常的组件通信中使用,因为它们破坏了组件的封装性…...
Util和utils
Util FieldStats 这段代码定义了一个名为FieldStats的Java类,位于com.cqupt.software_1.Util包中。它使用了lombok库的Data和AllArgsConstructor注解,这些注解帮助生成了getter、setter、toString等方法,以及包含所有参数的构造函数。类中有…...
拷贝构造、移动构造、拷贝赋值、移动赋值
最近在学习C的拷贝构造函数时发现一个问题:在函数中返回局部的类对象时,并没有调用拷贝构造函数。针对这个问题,查阅了一些资料,这里记录整理一下。 调用拷贝构造函数的三种情况: ① 用一个类去初始化另一个对象时&a…...
Python3 笔记:math模块
要使用 math 函数必须先导入math模块 语法:import math Python math 模块提供了许多对浮点数的数学运算函数。 math 模块下的函数,返回值均为浮点数,除非另有明确说明。 如果需要计算复数,需使用 cmath 模块中的同名函数。 m…...
python -【四】函数
函数 一、函数的基础 函数:是组织好的,可以重复使用的,用来实现特定功能的代码段 语法 def 函数名(入参): return 出参 # 定义函数 def out_hello():print(hello ~~~)# 调用/使用/执行函数 out_hello()练习题 自定义一个函数,…...
力扣 5. 最长回文子串 python AC
动态规划 class Solution:def longestPalindrome(self, s):size len(s)maxl 1start 0dp [[False] * size for _ in range(size)]for i in range(size):dp[i][i] Truefor L in range(2, size 1):for i in range(size):j L i - 1if j > size:breakif s[i] s[j]:if L…...
【微机原理及接口技术】可编程计数器/定时器8253
【微机原理及接口技术】可编程计数器/定时器8253 文章目录 【微机原理及接口技术】可编程计数器/定时器8253前言一、8253的内部结构和引脚二、8253的工作方式三、8253的编程总结 前言 本篇文章就8253芯片展开,详细介绍8253的内部结构和引脚,8253的工作方…...
23种设计模式之一— — — —装饰模式详细介绍与讲解
装饰模式详细讲解 一、定义二、装饰模式结构核心思想模式角色模式的UML类图应用场景模式优点模式缺点 实例演示图示代码演示运行结果 一、定义 装饰模式(别名:包装器) 装饰模式(Decorator Pattern)是结构型的设计模式…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
