当前位置：首页 > 入门组 > 2013年NOIP普及组车站分级题解（洛谷P1983）— 图论与拓扑排序的实战应用

2013年NOIP普及组车站分级题解（洛谷P1983）— 图论与拓扑排序的实战应用

2个月前 (07-26)

一、题目解读

“车站分级”是2013年NOIP普及组的经典题目（洛谷P1983）。题目要求根据车次停靠信息，为每个车站分配级别：若某车站被所有车次停靠，则为最高级；若仅被部分车次停靠，则级别取决于其连接的非停靠站的级别。核心在于将实际问题转化为图论模型，通过拓扑排序求解。

二、解题思路

用户提供的代码采用图论+拓扑排序策略。首先，用邻接表（graph）存储车站间的“非停靠站→停靠站”边关系，入度数组（in_degree）记录每个车站的入边数。通过遍历每趟车次的停靠站，将非停靠站指向所有停靠站，构建有向图。随后利用拓扑排序计算每个站的级别：入度为0的站（无依赖）初始化级别为1，逐级传递并更新相邻站的级别，最终得到最高级别。

三、解题步骤详解

1. 输入处理：读取车站数n和车次数m，循环处理每趟车。

2. 构建图：

标记当前车次的停靠站（is_stop）。

遍历区间内非停靠站，向所有停靠站连边（若边不存在则添加），并增加停靠站的入度。

3. 拓扑排序：

初始化队列：入度为0的站加入队列，级别设为1。

循环直至队列为空：

取出队首站u，遍历其所有出边（v）。

更新v的级别：level[v] = max(level[v], level[u] + 1)，记录最高级别。

若v的入度减至0，则加入队列。

4. 输出结果：最高级别即为答案。

四、代码与注释

#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) {              // 入度为0则入队
                q.push(v);
            }
        }
    }
    
    cout << max_level << endl;
    return 0;
}

注释说明：代码通过邻接表构建有向图，利用拓扑排序的依赖关系计算车站级别，核心逻辑集中在边构建和拓扑排序过程。