P1983 [NOIP 2013 普及组] 车站分级 · 习题解析

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1983（NOIP 2013 普及组 T4），日期见页头。 两边不一致时信原站。

题目描述

一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求： 如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。

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

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

P1983 题面里那张 5 趟车次的运行表

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

输入格式

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

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

输出格式

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

说明/提示

对于 20% 的数据，1 ≤ n, m ≤ 10；对于 50% 的数据，1 ≤ n, m ≤ 100；对于 100% 的数据，1 ≤ n, m ≤ 1000。

输入输出样例

输入

9 2
4 1 3 5 6
3 3 5 6

输出

第一趟停 1、3、5、6，途经却没停的是 2 和 4 ⇒ level[2] < level[1]、level[2] < level[3]……

输入

输出

多了一趟 1 5 9，途经未停的是 2、3、4、6、7、8 ⇒ 又压出一级，答案变成 3。

1★ 先把题面翻译成边：停了 x、途经没停 y ⇒ level[y] < level[x]

★ 一句话就能读出来

「停靠了 x ⇒ 始发终点之间所有级别 ≥ level[x] 的都必须停靠」—— 反过来说：途经却没停的 y，级别一定比每个停靠站都低。

⇒ 连边 y → x，答案 = 最长链上的点数（拓扑序上跑一次最长路，真实车站初值 1）。 ⚠ 注意「途经」= 始发站到终点站之间 —— 车次开不到的地方什么都推不出来（第 ④ 步那个错法就栽在这儿）。

2⚠ 朴素连边：答案完全正确，可它连边都存不下

p1983Naive.cpp⚠ 未停 × 已停：边数爆炸（对拍参照物）

// ⚠ P1983 的朴素建图：**每个「途经未停」的 y 直接连到每个「停靠」的 x** —— 答案完全正确，可边数爆炸。
//
// 一趟车如果停了 p 站、途经未停 q 站，这样连要 **p × q** 条边。
// 顶格 n = m = 1000、一趟车 500 停 500 未停 ⇒ 一趟 25 万条、1000 趟 **2.5 × 10⁸** 条 ——
// 光存边就要几个 GB。
//
// ★ 它是本页的**对拍参照物**（和虚点那条路建的是完全不同的图，答案必须一样），
//   也是「虚点值多少」那笔账的分母。
//
// ⚠ 命令行给一个 `count` 参数，它就只打「一共连了多少条边」。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    bool countOnly = (argc > 1 && string(argv[1]) == "count");
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);
    vector<char> stop(n + 1);
    long long edges = 0;

    for (int i = 1; i <= m; i++) {
        int s;
        cin >> s;
        vector<int> a(s);
        for (int& x : a) cin >> x;
        fill(stop.begin(), stop.end(), 0);
        for (int x : a) stop[x] = 1;
        for (int y = a.front(); y <= a.back(); y++) {
            if (stop[y]) continue;
            for (int x : a) { g[y].push_back(x); indeg[x]++; edges++; }   // ★ 未停 × 已停
        }
    }
    if (countOnly) { printf("%lld\n", edges); return 0; }

    vector<int> dis(n + 1, 1), box;
    for (int i = 1; i <= n; i++) if (!indeg[i]) box.push_back(i);
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (int v : g[u]) {
            dis[v] = max(dis[v], dis[u] + 1);
            if (--indeg[v] == 0) box.push_back(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dis[i]);
    printf("%d\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

一趟车停 p 站、途经未停 q 站 ⇒ 这样连要 p × q 条边。

★★★ 顶格实测：2.5 亿条边、1.40 秒、987 MB

造一档最坏形状（n = m = 1000，每趟车跑全程、恰好一半停一半不停）， A 机 · WSL2 · i5-13500H · 2026-08-30，独占：

	边数	耗时	峰值内存
朴素连边	★ 249 991 000	1.40 秒	★ 987 MB
★ 虚点（下一步）	1 000 000	0.02 秒	12.5 MB
差	★ 250.0 倍	70 倍	79 倍
（题面给的）		1 秒	128 MB

⇒ 先 MLE 再 TLE —— 又一次第 24 章 P1853、第 28 章 P2704 那条： 这道题真正的关卡是内存，而「答案对但装不下」样例和对拍都看不见，只能算。

3★★ 虚点：把「未停 × 已停」拆成「未停 + 已停」

给每趟车新建一个点 t：所有「途经未停」的 y → t（边权 0），t → 所有「停靠」的 x（边权 1）。

    朴素：  y1 --+                虚点：  y1 --+
            y2 --+--> x1,x2,x3           y2 --+--> (t) --> x1,x2,x3
            y3 --+                       y3 --+
                 3 x 3 = 9 条                  3 + 3 = 6 条

一趟车的边数从 p × q 降到 p + q ≤ n ⇒ 总边数 O(nm) = 10⁶。

p1983.cpp★★ 虚点版，这一版就能 AC

// ★★ P1983 正解：**建图 + 拓扑序上求最长路**，而**难点全在建图** —— 靠「虚点」把边省下来。
//
// 题意翻译：一趟车停靠了 x、途经却没停 y ⇒ **level[y] < level[x]** ⇒ 连边 y → x。
// 答案 = 最长链上的点数（分层数）= 拓扑序上跑一次 `dis[v] = max(dis[u]) + 1`。
//
// ⚠⚠ 朴素连边是 **O(Σ(未停 × 已停))**：顶格 n = m = 1000，一趟车能有 500 停 × 500 未停
//   ⇒ 一趟 25 万条、1000 趟就是 **2.5 × 10⁸** 条边 —— 存都存不下。
//
// ★★★ 虚点：每趟车**新建一个点** t，
//     · 所有「途经未停」的 y  →  t   （边权 0）
//     · t → 所有「停靠」的 x        （边权 1）
//   一趟车的边数从「未停 × 已停」降到「未停 + 已停」≤ n。
//   ⇒ 总边数 O(nm) = **10⁶**，差三个数量级。解析页第 ③ 步量了这件事。
//
// ⚠ 边权是 0 / 1 两种，所以最长路那一步要按边权走：`dis[v] = max(dis[v], dis[u] + w)`。
//   真实车站的初值是 1（最低一级），虚点初值是 0。
//
// 复杂度 O(nm)。顶格 n = m = 1000。
//
// ⚠ 命令行给一个 `count` 参数，它就只打「一共连了多少条边」（拿去和朴素那版比）。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    bool countOnly = (argc > 1 && string(argv[1]) == "count");
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    int tot = n + m;                                  // n 个真实车站 + m 个虚点
    vector<vector<pair<int, int>>> g(tot + 1);        // (到哪儿, 边权)
    vector<int> indeg(tot + 1, 0);

    vector<char> stop(n + 1);
    long long edges = 0;
    for (int i = 1; i <= m; i++) {
        int s;
        cin >> s;
        vector<int> a(s);
        for (int& x : a) cin >> x;
        fill(stop.begin(), stop.end(), 0);
        for (int x : a) stop[x] = 1;
        int t = n + i;                                // ★ 这趟车的虚点
        for (int y = a.front(); y <= a.back(); y++) {  // ⚠ 只看始发站到终点站之间
            if (stop[y]) { g[t].push_back({y, 1}); indeg[y]++; edges++; }
            else { g[y].push_back({t, 0}); indeg[t]++; edges++; }
        }
    }

    if (countOnly) { printf("%lld\n", edges); return 0; }

    vector<int> dis(tot + 1, 0), box;
    for (int i = 1; i <= n; i++) dis[i] = 1;          // 真实车站最低一级
    for (int i = 1; i <= tot; i++) if (!indeg[i]) box.push_back(i);
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (auto [v, w] : g[u]) {
            dis[v] = max(dis[v], dis[u] + w);
            if (--indeg[v] == 0) box.push_back(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dis[i]);
    printf("%d\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

⚠ 边权变成 0/1 两种，所以最长路那一步要按边权走：dis[v] = max(dis[v], dis[u] + w)； 真实车站初值 1、虚点初值 0（第 ⑤ 步那个错法就栽在这一句上）。

4⚠ 第一个错法：把「途经」当成了全部车站 —— 而它两个方向都会错

p1983Range.cpp✗ 把 1..n 全当成途经

// ✗ P1983 错法一：**把「途经」当成了「全部车站 1..n」**。
//
// 题面写得很清楚：「如果这趟车次停靠了火车站 x，则**始发站、终点站之间**所有级别 ≥ x 的都必须停靠」——
// **只有始发站到终点站之间**的车站才算途经。车次开都没开到的地方，什么也推不出来。
//
// ★ 它凭空多连了一堆边 ⇒ 约束更紧 ⇒ 答案**恒 ≥ 正解**。
// ⚠ 而官方第一组样例挡不住它（那趟车从 1 开到 6，1..9 里只多出 7、8、9 三个站，
//   恰好不改变答案）—— 解析页第 ④ 步量了它要多久才现形。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    int tot = n + m;                                  // n 个真实车站 + m 个虚点
    vector<vector<pair<int, int>>> g(tot + 1);        // (到哪儿, 边权)
    vector<int> indeg(tot + 1, 0);

    vector<char> stop(n + 1);
    for (int i = 1; i <= m; i++) {
        int s;
        cin >> s;
        vector<int> a(s);
        for (int& x : a) cin >> x;
        fill(stop.begin(), stop.end(), 0);
        for (int x : a) stop[x] = 1;
        int t = n + i;                                // ★ 这趟车的虚点
        for (int y = 1; y <= n; y++) {                 // ★ 把全部车站都当成途经了
            if (stop[y]) { g[t].push_back({y, 1}); indeg[y]++; }
            else { g[y].push_back({t, 0}); indeg[t]++; }
        }
    }

    vector<int> dis(tot + 1, 0), box;
    for (int i = 1; i <= n; i++) dis[i] = 1;          // 真实车站最低一级
    for (int i = 1; i <= tot; i++) if (!indeg[i]) box.push_back(i);
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (auto [v, w] : g[u]) {
            dis[v] = max(dis[v], dis[u] + w);
            if (--indeg[v] == 0) box.push_back(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dis[i]);
    printf("%d\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

300 轮
被抓	161
比正解大的轮数	259（含相等）
⚠ 比正解小的轮数	★ 41

★★ 它为什么会把答案算「小」—— 41 ≡ 41，全是环闹的

凭空多连边，连着连着就连出了环（3 → 9 和 9 → 3 同时存在）。一有环，Kahn 就提前停下，剩下的点 dis 还停在初值 ⇒ 答案残了。

实测：那一版的图有环的轮数是 182，而它把答案算小的轮数是 41 —— 两者同时成立也是 41，一个不差 ⇒ 算小的全是环闹的。

⇒ ★★ 所以「这个错法往哪个方向错」这句话在这儿没法只答一个方向：它既会因为「约束更紧」而算大，也会因为「造出环、Kahn 提前停」而算小。 ⚠ 而官方两组样例正好各抓到一个方向（打出 3 和 1，答案是 2 和 3）。

5⚠⚠ 第二个错法只有虚点版才有 —— 而第三个错法反被虚点救了

p1983VirtInit.cpp✗ 虚点也当成一个车站给了初值 1

// ✗ P1983 错法三：**虚点也被当成了一个真车站**（初值也给 1）。
//
// 虚点是我们为了省边**凭空造出来**的中转站，它不是车站、不占级别。
// 给它初值 1，等于在每条「未停 → 虚点 → 已停」的路上白送了一级。
//
// ★ 它只会把级别推高 ⇒ 答案**恒 ≥ 正解**。
// ⚠⚠ 这个错法是**虚点这个技巧自带的**：朴素建图那一版根本没有虚点，也就没有这个坑 ——
//   ★ **换一种省空间的写法，就换来一批新的、原来不存在的错法。**

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    int tot = n + m;                                  // n 个真实车站 + m 个虚点
    vector<vector<pair<int, int>>> g(tot + 1);        // (到哪儿, 边权)
    vector<int> indeg(tot + 1, 0);

    vector<char> stop(n + 1);
    for (int i = 1; i <= m; i++) {
        int s;
        cin >> s;
        vector<int> a(s);
        for (int& x : a) cin >> x;
        fill(stop.begin(), stop.end(), 0);
        for (int x : a) stop[x] = 1;
        int t = n + i;                                // ★ 这趟车的虚点
        for (int y = a.front(); y <= a.back(); y++) {  // ⚠ 只看始发站到终点站之间
            if (stop[y]) { g[t].push_back({y, 1}); indeg[y]++; }
            else { g[y].push_back({t, 0}); indeg[t]++; }
        }
    }

    vector<int> dis(tot + 1, 0), box;
    for (int i = 1; i <= tot; i++) dis[i] = 1;        // ★ 连虚点一起给了 1
    for (int i = 1; i <= tot; i++) if (!indeg[i]) box.push_back(i);
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (auto [v, w] : g[u]) {
            dis[v] = max(dis[v], dis[u] + w);
            if (--indeg[v] == 0) box.push_back(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dis[i]);
    printf("%d\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

虚点是为了省边凭空造出来的中转站，它不是车站、不占级别。给它初值 1，等于在每条「未停 → 虚点 → 已停」的路上白送一级 ⇒ 恒 ≥ 正解（300 / 300），被抓 287 / 300。

⇒ ★★ 它是虚点这个技巧自带的错法 —— 朴素建图那一版根本没有虚点，也就没有这个坑。 换一种省空间的写法，就换来一批原来不存在的错法。

p1983Zero.cpp✗ 真实车站初值给了 0

// ✗ P1983 错法二：**真实车站的初值给了 0** —— 答案恒好少 1。
//
// 题面第一句就写着「每个火车站都有一个级别，**最低为 1 级**」。
// 初值给 0，算出来的是「最长链上有几条边」，而题目要的是「有几个级别」。
//
// ⚠ 官方样例一测就死（打 1 和 2，而答案是 2 和 3）。
//
// ⚠⚠ 而它在**顺手写的生成器**上几乎抓不到（300 轮只有 13 次）—— 这一条是被实测打回来的：
//   我原以为「它恒等于正解 − 1」，其实**虚点顺手把它救了** ——
//   只要某趟车真的**停靠**了某个站，那个站就会从虚点那里白得 `+1`，两版的 max 就一样了。
//   ⇒ 它只在「**这趟车有途经却没停的站**」时才差出那一级；
//     而顺手的生成器阈值一低就全停了，**根本造不出那种车次**（解析页第 ④ 步量了这条）。
//   ⇒ ★★ **换一个省空间的写法，连它掩盖哪些 bug 都跟着变了。**

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    int tot = n + m;                                  // n 个真实车站 + m 个虚点
    vector<vector<pair<int, int>>> g(tot + 1);        // (到哪儿, 边权)
    vector<int> indeg(tot + 1, 0);

    vector<char> stop(n + 1);
    for (int i = 1; i <= m; i++) {
        int s;
        cin >> s;
        vector<int> a(s);
        for (int& x : a) cin >> x;
        fill(stop.begin(), stop.end(), 0);
        for (int x : a) stop[x] = 1;
        int t = n + i;                                // ★ 这趟车的虚点
        for (int y = a.front(); y <= a.back(); y++) {  // ⚠ 只看始发站到终点站之间
            if (stop[y]) { g[t].push_back({y, 1}); indeg[y]++; }
            else { g[y].push_back({t, 0}); indeg[t]++; }
        }
    }

    vector<int> dis(tot + 1, 0), box;
    for (int i = 1; i <= n; i++) dis[i] = 0;          // ★ 从 0 开始
    for (int i = 1; i <= tot; i++) if (!indeg[i]) box.push_back(i);
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (auto [v, w] : g[u]) {
            dis[v] = max(dis[v], dis[u] + w);
            if (--indeg[v] == 0) box.push_back(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dis[i]);
    printf("%d\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

⚠⚠ 这一条是我的草稿被实测打回来的：它并不「恒等于正解 − 1」

草稿写的是「初值 0 ⇒ 算的是最长链上的边数，恒等于正解 − 1」。 实测顺手随机 300 轮只被抓 13 次。

真因：虚点顺手把它救了 —— 只要某个站被某趟车停靠过，它就会从那个虚点得到 +1，两版的 max 就一样了。只有当最长链的起点是一个从没被任何车次停靠过的站时，那一级才差得出来。

300 轮	顺手随机（档位 0）	★ 保证每趟车都有「途经未停」站（档位 3）
「初值 0」被抓	★ 13	★ 231
而「有途经未停的车次」的轮数	56	★ 231（一个不差）
「有从没被停靠过的车站」的轮数	194	268

⚠ 顺手写的生成器为什么造不出「途经未停」的车次：它挑的阈值一低，区间里的站就全停了 —— 而没有未停站的车次一条边都不产生。 ⇒ ★★ 又一次「顺手写的生成器的默认档，正是某个 bug 的藏身处」。

6⚠⚠ 这道题最难写的不是正解，是生成器

题面写着「输入保证所有的车次都满足要求」。而随手给每趟车挑一组停靠站，多半是非法输入。

★ 造合法输入要反着来 —— 而「合法」有一个能跑的判据

判据：一组车次合法 ⟺ 存在一种级别分配同时满足它们 ⟺ 派生出的「未停 → 已停」图无环。

实测（n = 8、3 趟车，随机挑停靠站）：2000 轮里只有 1490 轮（74.5%）是合法输入。

⇒ 生成器的正确做法是反着造：先给每个车站随机定一个级别，再照题面那条规则派生车次 —— 挑一段 [l, r] 和一个阈值 t，停靠站 = 这一段里所有级别 ≥ t 的车站。这样「停了 x 就必须停所有级别 ≥ 的站」自动成立。

⇒ 又一次第 13 章 P1162 那条： 有一类题最难写的不是正解，是生成器；而构造出来的输入也得拿题面的定义再验一遍。

7★ 对拍这一页

300 轮（`n` 随机 4~9，参照物 = 朴素建图）
虚点版 ≡ 朴素版	★ 不一致 0 轮
把 1..n 全当途经	161（★ 其中 41 轮算小了 —— 造出了环）
虚点也给初值 1	287（恒 ≥ 正解 300/300）
真实车站初值 0	13 →（保证有未停站的档）★ 231

顶格 n = m = 1000：虚点版边数 O(nm) = 10⁶；朴素最坏 (n/2)² · m = 2.5 × 10⁸。

8度量程序和生成器

p1983Count.cpp度量程序（本页所有数字都出自它）

p1983Gen.cpp数据生成器

9一页纸


★ 关键的一步	停了 x、途经没停 y ⇒ `y → x`；答案 = 最长链上的点数
★★★ 难点全在建图	朴素 2.5 亿条边（1.40 秒 / 987 MB，题面只给 128 MB）；虚点 10⁶ 条（0.02 秒 / 12.5 MB）—— 250 倍
⚠ 第一个错法	「途经」写成 1..n ⇒ 两个方向都错：算大（约束更紧）和算小（造出环 41 ≡ 41）
★★ 第二个错法是虚点自带的	虚点也给初值 1 ⇒ 恒 ≥ 正解（287/300）——换个写法就换来一批新错法
⚠⚠ 草稿被打回	「初值 0 恒等于正解 − 1」是错的：虚点把它救了（13/300 → 换档 231/300）
⚠⚠ 最难写的是生成器	随手挑停靠站只有 74.5% 合法；要反着造（先定级别、再派生车次）

洛谷 P1983 [NOIP 2013 普及组] 车站分级

0题目原文（本地存了一份）

输入

输出

输入

输出

1★ 先把题面翻译成边：停了 x、途经没停 y ⇒ level[y] < level[x]

2⚠ 朴素连边：答案完全正确，可它连边都存不下

3★★ 虚点：把「未停 × 已停」拆成「未停 + 已停」

4⚠ 第一个错法：把「途经」当成了全部车站 —— 而它两个方向都会错

5⚠⚠ 第二个错法只有虚点版才有 —— 而第三个错法反被虚点救了

6⚠⚠ 这道题最难写的不是正解，是生成器

7★ 对拍这一页

8度量程序和生成器

9一页纸