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

2024-01-06 01:28

本文主要是介绍洛谷——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;
}

这篇关于洛谷——P1983 [NOIP2013 普及组] 车站分级(拓扑排序、c++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/574782

相关文章

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快