洛谷——P1983 [NOIP2013 普及组] 车站分级(拓扑排序、c++)

文章目录

  • 一、题目
  • [NOIP2013 普及组] 车站分级
    • 题目背景
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 样例 #2
      • 样例输入 #2
      • 样例输出 #2
    • 提示
  • 二、题解
    • 基本思路:
    • 代码


一、题目

[NOIP2013 普及组] 车站分级

题目背景

NOIP2013 普及组 T4

题目描述

一条单向的铁路线上,依次有编号为 1 , 2 , … , n 1, 2, …, n 1,2,,n 的 $n $ 个火车站。每个火车站都有一个级别,最低为 1 1 1 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。
注意:起始站和终点站自然也算作事先已知需要停靠的站点。

例如,下表是 5 趟车次的运行情况。其中,前 4 趟车次均满足要求,而第 5 5 5 趟车次由于停靠了 3 3 3 号火车站( 2 2 2 级)却未停靠途经的 6 6 6 号火车站(亦为 2 2 2 级)而不满足要求。

现有 m m m 趟车次的运行情况(全部满足要求),试推算这 $ n$ 个火车站至少分为几个不同的级别。

输入格式

第一行包含 2 2 2 个正整数 n , m n, m n,m,用一个空格隔开。

i + 1 i + 1 i+1 ( 1 ≤ i ≤ m ) (1 ≤ i ≤ m) (1im) 中,首先是一个正整数 s i ( 2 ≤ s i ≤ n ) s_i\ (2 ≤ s_i ≤ n) si (2sin),表示第 $ i$ 趟车次有 s i s_i si 个停靠站;接下来有 $ s_i$ 个正整数,表示所有停靠站的编号,从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

输出格式

一个正整数,即 n n n 个火车站最少划分的级别数。

样例 #1

样例输入 #1

9 2 
4 1 3 5 6 
3 3 5 6

样例输出 #1

2

样例 #2

样例输入 #2

9 3 
4 1 3 5 6 
3 3 5 6 
3 1 5 9

样例输出 #2

3

提示

对于 $ 20%$ 的数据, 1 ≤ n , m ≤ 10 1 ≤ n, m ≤ 10 1n,m10

对于 50 % 50\% 50% 的数据, 1 ≤ n , m ≤ 100 1 ≤ n, m ≤ 100 1n,m100

对于 100 % 100\% 100% 的数据, 1 ≤ n , m ≤ 1000 1 ≤ n, m ≤ 1000 1n,m1000

二、题解

基本思路:

  • 题目让求n 个火车站最少划分的级别数。如果火车停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。
  • 也就是说不是停靠站的火车站级别必须是比停靠站的级别小的,这就给出了点与点之间的关系。建图完毕后,拓扑排序中取级别较大的即可

代码

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define fi first
#define se second
#define repn(i,o,n) for(int i=o;i<=n;i++)
#define rep(i,o,n) for(int i=o;i<n;i++)
const int N = 1010;
int n,m,a[N],rd[N];
vector<int> edge[N];//存图 
bool b[N],vis[N][N];//标记哪些是停靠站、是否已有边 queue<pair<int,int>> q; //车站编号、级别 
inline void TopoSort(){int res=0;//记录级别最大的即为答案 repn(i,1,n)if(!rd[i]) q.push({i,1});//入度为0的,最低级的入队 while(!q.empty()){auto x=q.front();q.pop()	;//cout<<x.fi<<' '<<x.se<<endl;for(auto y:edge[x.fi])if(--rd[y]==0){q.push({y,x.se+1});res=max (res,x.se+1);//取级别较大的 }}cout<<res<<endl;
}void solve() {cin>>n>>m;//建图 repn(i,1,m){memset(b,false,sizeof(b));int len;cin>>len;repn(j,1,len)cin>>a[j],b[a[j]]=true;//连边、建图 repn(j,a[1],a[len]){//从a[1](起始站)到a[len](终点站) if(b[j]) continue;//是停靠站repn(k,1,len){//len个停靠站 if(vis[j][a[k]]) continue;//已有边vis[j][a[k]]=true;rd[a[k]]++;//该停靠站入度加1 edge[j].push_back(a[k]);} }}TopoSort();
}signed main() {//IOS;int T=1;//cin>>T;while(T--) {solve();}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/231811.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

免费的GPT4来了,你还不知道吗?

程序员的公众号&#xff1a;源1024&#xff0c;获取更多资料&#xff0c;无加密无套路&#xff01; 最近整理了一波电子书籍资料&#xff0c;包含《Effective Java中文版 第2版》《深入JAVA虚拟机》&#xff0c;《重构改善既有代码设计》&#xff0c;《MySQL高性能-第3版》&…

Maven(mvn)的学习下载和配置

文章目录 Maven&#xff08;mvn&#xff09;1.Maven 是什么&#xff1f;2.Maven做什么&#xff1f;2.1传统方式对项目的管理2.2Maven对jar包的管理 3.Maven怎么学3.1Maven如何创建项目3.2Maven的下载与配置3.3Maven的项目结构3.4Maven依赖的引入3.5Maven依赖的剔除3.6Maven依赖…

2023 hnust 湖南科技大学 大四上 计算机图形图像技术 课程 期末考试 复习资料

计算机图形图像技术复习资料 前言 改编自&#xff1a;https://blog.csdn.net/Liu_Xin233/article/details/135232531★重点&#xff0c;※补充github 考试题型 简述题&#xff08;10分4题&#xff0c;共40分&#xff09; 第1章的基本内容三维观察流水线中的基本概念与理解三…

【面试高频算法解析】算法练习6 广度优先搜索

前言 本专栏旨在通过分类学习算法&#xff0c;使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目&#xff0c;帮助您深度理解每种算法&#xff0c;避免出现刷了很多算法题&#xff0c;还是一知半解的状态 专栏导航 二分查找回溯&#xff08;Backtracking&…

【Python机器学习】k近邻——模型复杂度与泛化能力的关系

以某数据进行研究&#xff0c;先将数据集分为训练集和测试集&#xff0c;然后用不同的邻居数对训练集合测试集的新能进行评估&#xff1a; from sklearn.datasets import load_breast_cancer from sklearn.model_selection import train_test_split from sklearn.neighbors imp…

日程安排小程序实战教程

日常中我们经常有一些事情需要提醒自己&#xff0c;使用日历的形式比较符合实际的使用习惯。本篇我们就利用微搭低代码工具带着大家开发一款日程安排的小程序。 1 创建数据源 登录微搭低代码控制台&#xff0c;打开数据模型&#xff0c;点击创建 输入数据源的名称日程安排 …

记录第一次在GitHub上面提交Issue

第一次在GitHub上面提交Issue&#xff0c;记录一下。 对着源码调了好久才发现&#xff0c;问题并不在程序而在模型&#xff08;虽然只是一个很小的问题&#xff0c;但是能够解决问题&#xff0c;并且做出了自己的一点小小贡献&#xff0c;还是很开心。嘻嘻&#xff0c;发博客记…

BART论文解读:BERT和GPT结合起来会发生什么?

BART:Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension 主要工作 提出了BART (Bidirectional and Auto-Regressive Transformers)&#xff0c; 是一种用于自然语言生成、翻译和理解的序列到序列的预训练方法。它…

stable diffusion 基础教程-提示词之光的用法

基图 prompt: masterpiece,best quality,1girl,solo,looking at viewer,brown hair,hair between eyes,bangs,very long hair,red eyes,blush,bare shoulders,(white sundress),full body,Negative prompt: EasyNegative,badhandv4,nsfw,lowres,bad anatomy,bad hands,text…

【DevOps-07-2】Sonarqube基本使用

一、简要说明 Sonar Qube的使用方式很多&#xff0c;Maven可以整合&#xff0c;也可以采用sonar-scanner的方式&#xff0c;再查看Sonar Qube的检测效果 Sonarqube集成在Maven实现代码检测使用sonar-scanner客户端的方式 二、Sonarqube管理后台安装中文插件 1、登录Sonarqube管…

数据结构和算法-插入排序(算法效率 折半优化 顺序表与链表插入排序 代码实现)

文章目录 插入排序算法实现算法效率分析优化-折半插入排序代码实现对链表进行插入排序小结 插入排序 首先49当作第一个已经排好序得元素&#xff0c;将第二个元素与前面得元素对比&#xff0c;发现小于49&#xff0c;于是49移动位置 此时将65与之前元素对比&#xff0c;发现其…

C语言编译器(C语言编程软件)完全攻略(第二部分:与编译器相关的几个知识点)

介绍常用C语言编译器的安装、配置和使用。 二、与编译器相关的几个知识点 上节我们介绍了编译器和 IDE 的概念&#xff0c;大家肯定希望赶紧实践一下&#xff0c;用 IDE 真正地运行一段C语言代码来看看效果&#xff0c;这样能够更快地获得成就感。 但是&#xff0c;使用 IDE …

Linux第20步_在虚拟机上安装“Visual Studio Code”

1、双击windows系统桌面上的“FileZilla Client.exe”&#xff0c;打开FTP客户端&#xff0c;点击03软件下的Visual Studio Code&#xff0c;发现code_1.50.1-1602600906_amd64。 2、点击“文件”&#xff0c;然后点击“站点管理器”&#xff0c;见下图操作&#xff1a; 3、点…

vr体验馆用什么软件计时计费,如遇到停电软件程序如何恢复时间

vr体验馆用什么软件计时计费&#xff0c;如遇到停电软件程序如何恢复时间 一、软件程序问答 如下图&#xff0c;软件以 佳易王vr体验馆计时计费软件V17.9为例说明 1、软件如何计时间&#xff1f; 点击相应编号的开始计时按钮即可 2、遇到停电再打开软件时间可以恢复吗&…

在 Oracle 数据库表中加载多个数据文件

在本文中&#xff0c;我将展示 SQL 加载器 Unix 脚本实用程序的强大功能&#xff0c;其中 SQL 加载器可以使用自动 shell 脚本加载多个数据文件。这在处理大量数据以及需要将数据从一个系统移动到另一个系统时非常有用。 它适合涉及大量历史数据的迁移项目。那么就不可能为每…

自然语言处理24-T5模型的介绍与训练过程,利用简单构造数据训练微调该模型,体验整个过程

大家好,我是微学AI,今天给大家介绍一下自然语言处理24-T5模型的介绍与训练过程,利用简单构造数据训练微调该模型,体验整个过程。在大模型ChatGPT发布之前,NLP领域是BERT,T5模型为主导,T5(Text-to-Text Transfer Transformer)是一种由Google Brain团队在2019年提出的自然…

大数据概念:数据网格和DataOps

数据网格&#xff08;Data Mesh&#xff09; 一种新型的数据架构模式&#xff0c;旨在解决传统数据架构中存在的一些问题&#xff0c;例如数据孤岛、数据冗余、数据安全等。数据网格将数据作为一种服务&#xff0c;通过在分布式环境中提供数据服务&#xff0c;实现数据的共享和…

多内层神经网络具有先天的不可解释性

多层神经网络的不可解释性是指其内部的决策过程很难被人类理解和解释。这主要是因为多层神经网络具有大量的神经元和多个层次的连接&#xff0c;使得网络的决策过程变得非常复杂。 具体而言&#xff0c;多层神经网络中每一层的神经元会根据输入的特征进行加权组合和非线性变换&…

Centos服务器安装Certbot以webroot的方式定时申请SSL免费证书

最近发现原先免费一年的SSL证书都改为3个月的有效期了&#xff0c;原先一年操作一次还能接受&#xff0c;现在3个月就要手动续期整的太慢烦了&#xff0c;还是让程序自动给处理下吧&#xff0c; 安装 Certbot yum install epel-release -y yum install certbot -yEPEL是由 Fe…

系统安全及应用

文章目录 系统安全及应用一、账号安全基本措施1、系统账号清理1.1 将用户设置为无法登录1.2 锁定长期不使用的账号1.3 删除无用的账户1.4 清空一个账号密码1.5 锁定账户文件passwd、shadow 2、密码安全控制设置密码有效期 3、命令历史限制3.1 减少命令记录条数3.2 登录时自动清…