[NOIP 2013 普及组] 车站分级

题意

给出若干趟车的停靠站。一趟车始发站到终点站之间，所有不停靠站的级别都必须低于每个停靠站。求满足全部约束时最少需要多少个级别。

思路

直接从每个不停靠站向每个停靠站连边，单趟车可能产生 $O(n^2)$ 条边。为每趟车建立一个虚拟节点 T：

不停靠站 u -> T，边权 0；
T -> 停靠站 v，边权 1。

令 level[x] 表示满足约束的最低级别。沿边转移：

level[v]=\max(level[v],level[u]+weight)

权值 0 只是把所有不停靠站的最大级别汇总到虚拟节点，权值 1 再保证每个停靠站至少高一级。这样单趟车只需线性数量的边。

样例一中关键站点的最低级别可以写成：

车站	是否受“不停靠 < 停靠”约束	最低级别
`2,4`	区间内不停靠站	`1`
`1,3,5,6`	停靠站，必须高于 `2,4`	`2`
`7,8,9`	没有更高要求	`1`

因此最少需要 2 级。对整个压缩 DAG 做拓扑最长路，即可同时满足所有车次约束。

Python 知识

每趟车的 set(stops) 支持快速判断区间车站是否停靠。
虚拟节点编号为 n+train，无需额外对象。
为节省大量二元组对象，代码把 (neighbor,weight) 编码成整数 (neighbor<<1)|weight。
解码时 edge>>1 取邻点，edge&1 取 0/1 权值。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：集合成员判断和 deque。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：大量元组的对象内存成本。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41import sys
from collections import deque


def main():
    read = sys.stdin.buffer.readline
    n, train_count = map(int, read().split())
    total_nodes = n + train_count
    graph = [[] for _ in range(total_nodes)]
    indegree = [0] * total_nodes

    for train in range(train_count):
        row = list(map(int, read().split()))
        stops = [station - 1 for station in row[1:]]
        stop_set = set(stops)
        virtual = n + train

        for station in range(stops[0], stops[-1] + 1):
            if station not in stop_set:
                graph[station].append(virtual << 1)
                indegree[virtual] += 1
        for station in stops:
            graph[virtual].append((station << 1) | 1)
            indegree[station] += 1

    level = [1] * n + [0] * train_count
    queue = deque(node for node in range(total_nodes) if indegree[node] == 0)
    while queue:
        node = queue.popleft()
        for edge in graph[node]:
            neighbor, weight = edge >> 1, edge & 1
            level[neighbor] = max(level[neighbor], level[node] + weight)
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    print(max(level[:n]))


if __name__ == "__main__":
    main()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * P1983 车站分级
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

const int MAXN = 1005;
const int MAXM = 1000005;

int head[MAXN * 2], to[MAXM], nxt[MAXM], w[MAXM], cnt;
int indeg[MAXN * 2];
int level[MAXN * 2];
int n, train_count;

void add_edge(int u, int v, int weight) {
    ++cnt;
    to[cnt] = v;
    w[cnt] = weight;
    nxt[cnt] = head[u];
    head[u] = cnt;
    ++indeg[v];
}

int main() {
    scanf("%d%d", &n, &train_count);
    int total = n + train_count; // 真实站 + 虚拟站
    for (int t = 0; t < train_count; ++t) {
        int stop_cnt;
        scanf("%d", &stop_cnt);
        int stops[MAXN], stop_set[MAXN] = {0};
        for (int i = 1; i <= stop_cnt; ++i) {
            scanf("%d", &stops[i]);
            stop_set[stops[i]] = 1;
        }
        int virtual_node = n + t + 1;
        // 未停靠的站 → 虚拟站（权 0）
        for (int s = stops[1]; s <= stops[stop_cnt]; ++s) {
            if (!stop_set[s]) add_edge(s, virtual_node, 0);
        }
        // 虚拟站 → 停靠的站（权 1）
        for (int i = 1; i <= stop_cnt; ++i)
            add_edge(virtual_node, stops[i], 1);
    }
    queue<int> q;
    for (int i = 1; i <= total; ++i)
        if (indeg[i] == 0) q.push(i);
    int ans = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            level[v] = max(level[v], level[u] + w[i]);
            --indeg[v];
            if (indeg[v] == 0) q.push(v);
        }
        if (u <= n) ans = max(ans, level[u]);
    }
    printf("%d\n", ans);
    return 0;
}

复杂度

设所有车次覆盖区间长度与停靠站数之和为 E，有 E<=O(mn)。建图和拓扑 DP 时间复杂度 $O(n+m+E)$ ，空间复杂度 $O(n+m+E)$ 。

总结

虚拟节点把一组到一组的完整约束压成两层边；0/1 权值再准确表达“汇总”和“必须高一级”。

[NOIP 2013 普及组] 车站分级

目录

题意

思路

Python 知识

代码

复杂度

总结