| 题目名称 | 1444. [NOIP 2013]车站分级 |
|---|---|
| 输入输出 | level2013.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 铁策
于2013-11-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：187， 提交：492， 通过率：38.01% | ||||
 LGLJ |
100 | 0.074 s | 6.71 MiB | C++ |
 jekyll |
100 | 0.078 s | 0.25 MiB | C++ |
|
jekyll |
100 | 0.082 s | 0.22 MiB | C++ |
|
jekyll |
100 | 0.097 s | 0.22 MiB | C++ |
 TA |
100 | 0.160 s | 8.09 MiB | C++ |
 Rapiz |
100 | 0.174 s | 0.30 MiB | C++ |
|
TA |
100 | 0.240 s | 15.66 MiB | C++ |
 KCkwok |
100 | 0.263 s | 1.28 MiB | C++ |
 Youngsc |
100 | 0.269 s | 4.47 MiB | C++ |
 梦那边的美好ET |
100 | 0.286 s | 4.14 MiB | C++ |
| 本题关联比赛 | |||
| 暑假综合模拟2 | |||
| 关于 车站分级 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这种建图也真是惊人
┭┮﹏┭┮
2023-11-23 17:41
17楼
| ||||
|
退役预定
LGLJ
2019-07-22 15:50
16楼
| ||||
|
拓扑排序
 Shirry
2017-09-11 21:43
15楼
| ||||
|
好神奇的Toposort
| ||||
|
普及组的题并不都很简单啊. 注意用邻接矩阵防止重边
 小e
2016-11-11 07:06
13楼
| ||||
|
奇怪的WA一个- -
| ||||
|
本机AC，交上来就错了，卡了快一年。发现居然是文件名多打了一个空格。
 /k
2016-04-07 16:10
11楼
| ||||
|
普及组的题也不可小视......
| ||||
|
bitset真是牛逼。。
TA
2015-06-27 10:18
9楼
| ||||
|
有没有强大的优化呢
| ||||
FoolMike
神利·代目
forever【题目描述】
一条单向的铁路线上，依次有编号为1, 2, …, n的n个火车站。每个火车站都有一个级别，最低为1级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站x，则始发站、终点站之间所有级别大于等于火车站x的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）
例如，下表是5趟车次的运行情况。其中，前4趟车次均满足要求，而第5趟车次由于停靠了3号火车站（2级）却未停靠途经的6号火车站（亦为2级）而不满足要求。
现有m趟车次的运行情况（全部满足要求），试推算这n个火车站至少分为几个不同的级别。
【输入格式】
第一行包含2个正整数n, m，用一个空格隔开。
第i+1行（1≤i≤m）中，首先是一个正整数s_i（2≤s_i≤n），表示第i趟车次有s_i个停靠站；接下来有s_i个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。
【输出格式】
输出只有一行，包含一个正整数，即n个火车站最少划分的级别数。
【样例输入1】
9 2 4 1 3 5 6 3 3 5 6
【样例输出1】
2
【样例输入2】
9 3 4 1 3 5 6 3 3 5 6 3 1 5 9
【样例输出2】
3
【提示】
对于20%的数据，1 ≤ n, m ≤ 10；
对于50%的数据，1 ≤ n, m ≤ 100；
对于100%的数据，1 ≤ n, m ≤ 1000。
【来源】
NOIP2013普及组第四题