作业帮 > 综合 > 作业

noip2013 普及组复赛 车站分级

来源：学生作业帮 编辑：搜搜做题作业网作业帮 分类：综合作业 时间：2024/05/04 20:53:23
noip2013 普及组复赛 车站分级

4．车站分级 

(level.cpp/c/pas) 

 

【问题描述】 

一条单向的铁路线上，依次有编号为 1, 2, …, n的n个火车站。每个火车站都有一个级

别，最低为1级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车

次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。（注

意：起始站和终点站自然也算作事先已知需要停靠的站点） 

例如，下表是5趟车次的运行情况。其中，前4趟车次均满足要求，而第 5趟车次由于

停靠了3号火车站（2 级）却未停靠途经的 6号火车站（亦为 2 级）而不满足要求。 

现有m趟车次的运行情况（全部满足要求），试推算这 n 个火车站至少分为几个不同的

级别。 

 

【输入】 

输入文件为level.in。 

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

第i + 1 行（1 ≤ i ≤ m）中，首先是一个正整数 si（2 ≤ si ≤ n），表示第i趟车次有 si 个停

靠站；接下来有si个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个

空格隔开。输入保证所有的车次都满足要求。 

 

【输出】 

输出文件为level.out。 

输出只有一行，包含一个正整数，即 n 个火车站最少划分的级别数。 

 

【输入输出样例】 

level.in  level.out 

9 2  2 

4 1 3 5 6   

3 3 5 6 

 

9 3  3 

4 1 3 5 6   

3 3 5 6 

3 1 5 9 

 

 

【数据范围】 

对于20%的数据，1 ≤ n, m ≤ 10； 

对于50%的数据，1 ≤ n, m ≤ 100； 

对于100%的数据，1 ≤ n, m ≤ 1000。 

 






如上 求大神解……文库上的题解没看懂……求思路 可以不要程序Qwq


noip2013 普及组复赛 车站分级
拓扑排序。。。
先建边，每趟车不停的站指向有停的站，然后进行拓扑排序，排序次数即为答案
noip2011普及组复赛解题思路 求noip2011普及组复赛试题 2008noip普及组复赛解题报告 2008noip普及组复赛题 求NOIP2011复赛普及组题目详解 PASCAL noip2011普及组复赛浙江所有人的成绩 noip2011普及组复赛成绩什么时候出啊 求2008年NOIP普及组复赛试题 NOIP2008普及组复赛第4题标程大神们帮帮忙 紧急!NOIP2011普及组复赛,复测如果原来错的批下来还是错的, noip2011普及组复赛成绩什么时候出啊?哪里可以知道成绩啊?浙江赛区的 我想问一下,noip普及组复赛常考的题型大概有哪几类?还有如果考动态规划,大概是什么难度?还有复赛可以带U盘吗?