解析：完善程序-1

信息学奥赛历年真题 2023年CSP提高组真题解析：完善程序-1

问题分析：这段代码实现的是一个在有向无环图（DAG）中，找到按字典序排序的第k条最短路径的算法。输入是n个节点和m条边的DAG，以及一个整数k。目标是找到第k条最短路径的起点，并按照字典序输出后续路径上的节点。

🌟 例子：

图结构如下：

   0 → 1 → 3
   ↓   ↓
   2 → 4

顶点：0,1,2,3,4
边：
- 0→1, 0→2
- 1→3, 1→4
- 2→4

1. 所有路径表（至少 1 个点）

起点=0	起点=1	起点=2	起点=3	起点=4
[0]	[1]	[2]	[3]	[4]
[0,1]	[1,3]	[2,4]
[0,1,3]	[1,4]
[0,1,4]
[0,2]
[0,2,4]
6条	3条	2条	1条	1条

2. 总共有多少条路径？

总计 = 13 条路径

3. 按字典序排序

字典序比较规则：先比较第 1 个数，小的在前；如果相等再看下一个。

排完是这样：

[0]
[0,1]
[0,1,3]
[0,1,4]
[0,2]
[0,2,4]
[1]
[1,3]
[1,4]
[2]
[2,4]
[3]
[4]

4. 对应第 k 小

k=1 → [0]
k=5 → [0,2]
k=10 → [2]
k=13 → [4]

第 k 小路径，就是所有路径的“字典序排名”。

最后输出的是第 k 小路径的完整“顶点序列”（从起点到终点）。

代码分析：

数据结构：
- E[u] 是一个邻接表，存储从节点u到其他节点的边。
- deg[i] 记录每个节点的入度，方便进行拓扑排序。
- f[u] 记录从节点u开始的所有可能路径的数量，用于判断第k条路径起点的选择。
核心算法：
- 拓扑排序:
  - 将入度为0的节点入队，进行拓扑排序。
  - 拓扑排序的目的是为了按照节点的依赖关系进行遍历，确保在计算路径数量时，所有前驱节点的路径数量都已经计算完毕。
- 动态规划计算路径数量:
  - 从拓扑排序的结果逆序遍历节点。
  - 对于每个节点u，计算从u出发到所有后继节点的路径数量之和，并将其存储在f[u]中。
  - 为了防止路径数量过大，引入了一个上限LTM。
- 查找第k小的路径起点:
  - 使用next函数，在候选节点中找到第k小的路径的起点。
  - next函数通过对候选节点进行排序，并逐步减去每个节点对应的路径数量，来定位第k小的路径。
  - 找到起点后，输出，并继续查找第k-1小的路径，直到k=1。

代码实现：

/**************************************************************** 
 * Description: 2023_CSP_S_F01
 * Author: Alex Li
 * Date: 2024-06-18 13:56:33
 * LastEditTime: 2024-06-18 19:16:24
****************************************************************/
#include <iostream> 
#include <algorithm>
#include <vector>

const int MAXN = 100000;               // 定义最大节点数
const long long LTM = 1000000000000000000; // 定义一个很大的数，用于限制路径数量的上限
int n, m, deg[MAXN];                   // n: 节点数, m: 边数, deg: 每个节点的入度数组
std::vector<int> E[MAXN];              // 邻接表存储图的边关系
long long k, f[MAXN];                  // k: 要查找的第k小路径，f[i]: 从节点i开始的路径数量

// 在后选点中，找第k小的路径的起点
int next(std::vector<int> cand, long long &k) {
    std::sort(cand.begin(), cand.end()); // 对候选节点进行排序
    for(int u : cand) {                  // 遍历排序后的候选节点
        if(k <= f[u]) return u;          // 如果k在当前节点u对应的路径数量范围内，返回u作为起点
        k -= f[u];                       // 否则减去该节点对应的路径数量，继续下一个候选节点
    }
    return -1;                           // 如果找不到合适的节点，返回-1
}

int main() {
    std::cin >> n >> m >> k;             // 读入节点数n，边数m，和需要查询的第k小路径
    for(int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;              // 读入每条边的起点u和终点v
        E[u].push_back(v);               // 将边添加到邻接表E中，表示从u到v有一条边
        ++deg[v];                        // 增加节点v的入度
    }

    // 拓扑排序
    std::vector<int> Q;                  // 存储拓扑排序的结果
    for(int i = 0; i < n; ++i)
        if(!deg[i]) Q.push_back(i);      // 将所有入度为0的节点加入队列Q

    for(int i = 0; i < n; ++i) {
        int u = Q[i];                    // 依次处理拓扑序中的每个节点
        for(int v : E[u]) {              // 遍历该节点u的所有邻接节点v
            if(deg[v] == 1)              // 如果邻接节点v的入度为1，说明v的前驱都已处理
                Q.push_back(v);          // 将v加入拓扑序队列
            --deg[v];                    // 减少节点v的入度
        }
    }
    std::reverse(Q.begin(), Q.end());    // 将拓扑序逆序，方便后续动态规划计算路径数量

    // 动态规划计算f(i): 从i节点开始的路径数量
    for(int u : Q) {
        f[u] = 1;                        // 每个节点的路径数量初始为1（即单个节点本身）
        for(int v : E[u])                // 遍历该节点u的所有邻接节点v
            f[u] = std::min(f[u] + f[v], LTM); // 累加从v开始的路径数量，避免超过上限LTM
    }

    // 查找第k小的路径的起点
    int u = next(Q, k);
    std::cout << u << std::endl;         // 输出起点u

    // 如果需要依次找到第k-1, k-2的路径
    while(k > 1) {
        --k;                             // 递减k
        u = next(E[u], k);               // 查找当前节点u的邻接节点中第k小的路径
        std::cout << u << std::endl;     // 输出当前的节点
    }

    return 0;
}

Previous Topic

Back to Lesson

Next Topic