[NOIP 2013 普及组] 车站分级

题目解析：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. 代码结构分析

A. 链式前向星 (linklist 结构体)

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

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

cpp

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

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

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

4. 优化建议（进阶点）

建边去重（极其重要）：你的代码中 e.add 可能会针对同一对 (u, v) 重复建边多次。例如车次 1 要求 3>2，车次 2 也要求 3>2。

后果：rd[v] 会偏大，虽然最终 rd[v]==0 逻辑没错，但会产生大量冗余边，极大消耗内存和时间。
改进：使用 bool vis[maxn][maxn] 记录，若 vis[u][v] 已为 true，则不再建边。

查找优化： in_a 函数可以通过一个布尔数组 is_stop[1005] 优化到 O(1)。每趟车开始前 memset 为 0，停靠站设为 1。
虚拟节点（Space-Time Tradeoff）：对于每一趟车次，建立一个“中间虚拟节点”。让所有“未停靠站”连向“虚拟节点”，再由“虚拟节点”连向所有“停靠站”。这样边数从 O(N^2) 降到了 O(N)，是处理本题特大数据集的“黑科技”。

5. 总结

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

6. 代码

cpp

#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;
}