[NOIP 2013 普及组] 车站分级

标签: #noip #topsort
原题目: luogu-P1983
简要描述: topsort建模

题目解析：P1983 车站分级

1. 核心题意拆解

题目给出的规则可以简化为：在一趟车次的始发站和终点站之间，凡是停靠了的车站，其等级一定比未停靠的车站高。

  • 输入约束：给出 m 趟车次及每趟车停靠的站点。
  • 目标：求出满足所有约束条件的最小等级总数。

2. 算法建模：拓扑排序 + DAG 最长路

你的代码准确地捕捉到了问题的本质：等级之间的先后关系构成了一个有向无环图 (DAG)。

  • 建图逻辑： 对于每一趟车次，区间 [\text{始发站}, \text{终点站}] 内的车站被分为两个集合：
  • 集合 A (停靠站)：a[1], a[2], ..., a[t]。
  • 集合 B (未停靠站)：在该区间内但不在 a 数组中的车站。
  • 逻辑关系：对于任意 u \in \text{集合 A}，v \in \text{集合 B}，都有 \text{level}(u) > \text{level}(v)。
  • 代码实现：你在 init() 函数中通过 e.add(a[k], j, 1) 建立了由“高等级站”指向“低等级站”的边。

特别注意：你的代码中建立的是 停靠站 -> 未停靠站 的边，这意味着在计算最长路时，入度为 0 的点是等级最高的。通常习惯建立 未停靠站 -> 停靠站 的边（低到高），效果是一样的。

3. 代码结构分析

你使用了一个结构体封装了链式前向星，这是处理 N, M \le 1000 规模图论问题的标准做法，空间利用率高且遍历速度快。

B. 数据读入与建边 (init 函数)

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10

        for(int j=a[1];j<=a[t];j++){
    if(in_a(j,t)==false){ // 找到未停靠站
        for(int k=1;k<=t;k++){
            e.add(a[k],j,1); // 停靠站 -> 未停靠站
            rd[j]++;
        }
    }
}

这段代码实现了逻辑提取。不过要注意，in_a 的线性查找会导致建边复杂度达到 O(M \cdot N^2)。在 N=1000 时，如果数据很满，可能会面临 TLE（超时）风险。

C. 分层拓扑排序 (topsort 函数)

你利用 ans 数组记录每个点所在的层级：

cpp
copy 
        
1
2
3
4
5

        if(ans[u]+1 > ans[v]){
    ans[v] = ans[u] + 1; // 经典的 DAG 最长路递推
}

这保证了最终 ans 数组中存储的是从入度为 0 的点到该点的最长路径长度。

4. 优化建议（进阶点）

  1. 建边去重（极其重要）： 你的代码中 e.add 可能会针对同一对 (u, v) 重复建边多次。例如车次 1 要求 3>2，车次 2 也要求 3>2。
  • 后果：rd[v] 会偏大，虽然最终 rd[v]==0 逻辑没错，但会产生大量冗余边，极大消耗内存和时间。
  • 改进：使用 bool vis[maxn][maxn] 记录，若 vis[u][v] 已为 true，则不再建边。
  1. 查找优化： in_a 函数可以通过一个布尔数组 is_stop[1005] 优化到 O(1)。每趟车开始前 memset 为 0，停靠站设为 1。
  2. 虚拟节点（Space-Time Tradeoff）： 对于每一趟车次，建立一个“中间虚拟节点”。让所有“未停靠站”连向“虚拟节点”，再由“虚拟节点”连向所有“停靠站”。这样边数从 O(N^2) 降到了 O(N)，是处理本题特大数据集的“黑科技”。

5. 总结

你的代码逻辑非常清晰，是一个标准且优雅的拓扑排序应用示例。 它成功地将现实中的“分级规则”转化为了图论中的“拓扑序深度”问题。

6. 代码

cpp
copy 
        
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

        #include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int maxe = 2e6+5;
struct linklist{
    struct edge{
        int u,v,w,next;
    };
    edge e[maxe];
    int h[maxe];
    int cnt=0;
    linklist(){
        memset(h,-1,sizeof(h));
    }
    void add(int u,int v,int w) {
        cnt++;
        e[cnt].u = u;
        e[cnt].v = v;
        e[cnt].w =w;
        e[cnt].next = h[u];
        h[u] = cnt;
    }
    void add2(int u,int v,int w){
        add(u,v,w);
        add(v,u,w);
    }
} e;

int m,n;
int a[maxn];
int rd[maxn];

bool in_a(int s,int t){
    for(int j=1;j<=t;j++){
        if(s==a[j]){
            return true;
        }
    }
    return false;
}

void init(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        memset(a,0,sizeof(a));
        int t;
        cin >> t;
        for(int j=1;j<=t;j++){
            cin >> a[j];
        }
        for(int j=a[1];j<=a[t];j++){
            if(in_a(j,t)==false){
                for(int k=1;k<=t;k++){
                    e.add(a[k],j,1);
                    rd[j]++;
                }
            }
        }
    }
}

queue<int> q;
int ans[maxn];

void topsort() {
    for(int i = 1;i <= n ;++i ){
        if( rd[i] == 0) q.push(i);
    }
    while( !q.empty()){
        int u = q.front();
        q.pop();
        for(int i = e.h[u]; ~i;i = e.e[i].next) 
        {
            int v = e.e[i].v;
            rd[v]--;
            if(ans[u]+1>ans[v]){
                ans[v]=ans[u]+1;
            }
            if( rd[v] == 0)
                q.push(v);
        }
    }
}

int main(){
    init();
    topsort();
    int max1=-1;
    for(int i=1;i<=n;i++){
        max1=max(max1,ans[i]);
    }
    cout << max1+1;
    return 0;
}