2013年NOIP普及组车站分级（洛谷P1983）：拓扑排序算法实战指南

一、问题背景分析

车站分级是NOIP2013普及组的经典图论问题，要求根据列车停靠情况确定车站的最小分级数量。题目核心是建立非停靠站与停靠站之间的偏序关系，转化为有向无环图(DAG)的拓扑排序问题。

二、核心数据结构

const int MAXN = 1005;
vector<int> graph[MAXN];  // 邻接表存储车站依赖关系
int in_degree[MAXN];      // 记录每个车站的入度
int level[MAXN];          // 存储最终分级结果
bool is_stop[MAXN];       // 标记停靠站的临时数组
vector<int> stops;        // 存储每趟车的停靠站序列

三、算法实现详解

1. 输入处理阶段：

   while (m--) {
       int s; cin >> s;
       stops.clear();
       memset(is_stop, false, sizeof(is_stop));
       // 记录停靠站信息
       for (int i = 0; i < s; ++i) {
           int x; cin >> x;
           stops.push_back(x);
           is_stop[x] = true;
       }

• 读取n个车站和m趟列车信息

• 对每趟列车记录其停靠站序列

2. 建图阶段：

   for (int i = stops[0]; i <= stops.back(); ++i) {
       if (!is_stop[i]) {
           for (int j : stops) {
               if (find(graph[i].begin(), graph[i].end(), j) == graph[i].end()) {
                   graph[i].push_back(j);
                   in_degree[j]++;
               }
           }
       }
   }

• 建立非停靠站到停靠站的边

• 确保边的唯一性避免重复计算

3. 拓扑排序阶段：

   queue<int> q;
   for (int i = 1; i <= n; ++i) {
       if (in_degree[i] == 0) {
           q.push(i);
           level[i] = 1;
       }
   }
   
   while (!q.empty()) {
       int u = q.front(); q.pop();
       for (int v : graph[u]) {
           level[v] = max(level[v], level[u] + 1);
           if (--in_degree[v] == 0) {
               q.push(v);
           }
       }
   }

• 使用队列实现经典Kahn算法

• 动态更新车站级别

四、完整代码

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

const int MAXN = 1005;

vector<int> graph[MAXN];  // 邻接表存储图
int in_degree[MAXN];      // 入度数组
int level[MAXN];          // 记录每个站点的级别
bool is_stop[MAXN];       // 标记是否为停靠站
vector<int> stops;        // 临时存储每趟车的停靠站

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    while (m--) {
        int s;
        cin >> s;
        stops.clear();
        memset(is_stop, false, sizeof(is_stop));
        
        // 读取停靠站信息
        for (int i = 0; i < s; ++i) {
            int x;
            cin >> x;
            stops.push_back(x);
            is_stop[x] = true;
        }
        
        // 构建边的关系：非停靠站级别 < 停靠站级别
        for (int i = stops[0]; i <= stops.back(); ++i) {
            if (!is_stop[i]) {  // 非停靠站
                for (int j : stops) {  // 所有停靠站
                    if (find(graph[i].begin(), graph[i].end(), j) == graph[i].end()) {
                        graph[i].push_back(j);
                        in_degree[j]++;
                    }
                }
            }
        }
    }
    
    // 拓扑排序
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
            level[i] = 1;  // 初始级别为1
        }
    }
    
    int max_level = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : graph[u]) {
            level[v] = max(level[v], level[u] + 1);
            max_level = max(max_level, level[v]);
            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    cout << max_level << endl;
    return 0;
}