洛谷P1137题解：图论+动态规划旅游路线规划问题

一、问题分析

这道题目描述了一个旅游路线规划问题：有N个城市，M条有向道路（保证无环），需要计算以每个城市为终点时能够游览的最大城市数量。游览路线必须满足只能向东移动的条件。

二、解题思路

1. ‌图论模型‌：将城市看作节点，道路看作有向边，题目保证无环（DAG）

2. ‌动态规划‌：DP[i]表示以城市i为终点能游览的最大城市数

3. ‌拓扑排序‌：按照拓扑顺序计算dp值，确保计算顺序正确

三、关键算法

1. ‌拓扑排序‌：用于处理有向无环图(DAG)的节点顺序

2. ‌动态规划‌：利用递推关系式dp[v] = max(dp[v], dp[u] + 1)

四、完整代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    // 构建图的邻接表表示
    vector<vector<int>> graph(N + 1); // 1-based索引
    vector<int> inDegree(N + 1, 0);   // 记录每个节点的入度

    // 读取道路信息并构建图
    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y); // x -> y 的有向边
        inDegree[y]++;         // y的入度增加
    }

    // 初始化拓扑排序队列
    queue<int> q;
    vector<int> dp(N + 1, 1); // 每个城市至少能游览自己

    // 将入度为0的节点加入队列
    for (int i = 1; i <= N; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // 拓扑排序
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 遍历u的所有邻居
        for (int v : graph[u]) {
            // 更新v的最大游览城市数
            dp[v] = max(dp[v], dp[u] + 1);

            // 减少v的入度，如果入度为0则加入队列
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 输出结果
    for (int i = 1; i <= N; ++i) {
        cout << dp[i] << endl;
    }

    return 0;
}

五、代码解析

1. ‌输入处理‌：

• 读取城市数量N和道路数量M

• 构建邻接表表示的图结构

• 记录每个节点的入度

2. ‌拓扑排序‌：

• 初始化队列，将入度为0的节点加入

• 依次处理队列中的节点，更新其邻居的dp值和入度

3. ‌动态规划‌：

• 初始时每个城市dp值为1（至少包含自己）

• 在处理每个节点u时，更新所有邻居v的dp值

4. ‌输出结果‌：

• 按照城市编号顺序输出每个城市的dp值