2024 年 NOI 最后一题题解

问题描述

2024 年 NOI 最后一题是一道结合图论与动态规划的综合性算法题，题目要求解决带有时效性和资源约束的路径优化问题。具体描述如下：

给定一个有向图 G (V, E)，其中节点代表站点，边代表连接站点的路径。每条边具有三个属性：基础行驶时间 t、基础费用 c 和资源消耗 r。需要将一批重要物资从起点 S 运输到终点 T，要求满足以下约束：

1. 总行驶时间不超过 T_max
2. 总资源消耗不超过 R_max
3. 每条边的实际费用会随出发时间变化（模拟高峰期价格波动）

此外，每条边可以选择使用 "高速模式"：消耗额外 50% 的资源，减少 30% 的行驶时间，费用保持不变。请设计算法找到满足所有约束条件的最小总费用路径。

问题分析

这道题是经典最短路径问题的扩展，融合了多重约束和决策选择，主要挑战包括：

1. 三重约束：需要同时考虑时间、费用和资源三个维度
2. 时效性：边的费用随出发时间动态变化
3. 决策点：对每条边需要选择是否使用高速模式
4. 多目标优化：在满足约束条件下最小化总费用

问题可以转化为带约束的多维度最优化问题，需要使用扩展的最短路径算法结合动态规划思想来解决。

算法设计

我们采用改进的 Dijkstra 算法，结合三维动态规划来处理多重约束：

1. 状态表示：定义 dp [u][t][r] 为到达节点 u 时，累计时间为 t 且累计资源消耗为 r 的最小费用
2. 状态转移：对于每个状态 (u, t, r)，考虑所有从 u 出发的边 (u, v)：
   • 普通模式：新时间 t' = t + t_uv，新资源 r' = r + r_uv，新费用 c' = dp [u][t][r] + c_uv (t)
   • 高速模式：新时间 t' = t + 0.7t_uv，新资源 r' = r + 1.5r_uv，新费用 c' = dp [u][t][r] + c_uv (t)
3. 约束条件：t' ≤ T_max 且 r' ≤ R_max
4. 优先级队列：按费用排序，优先处理费用较低的状态

实现细节

1. 三维 DP 数组：由于时间和资源可能较大，需要合理设置精度和范围
2. 费用函数：实现随时间变化的费用计算，题目规定为工作日早晚高峰模式
3. 状态压缩：对于相同节点、时间和资源消耗，只保留最小费用状态
4. 决策处理：对每条边都考虑两种模式，分别计算并更新状态
5. 边界条件：起点初始状态设置和终点状态的筛选

复杂度分析

• 时间复杂度：O (E * T_max * R_max * log (V * T_max * R_max))，其中 E 为边数，V 为节点数，T_max 和 R_max 分别为时间和资源约束上限
• 空间复杂度：O (V * T_max * R_max)，主要用于存储三维 DP 数组

通过状态剪枝和优先队列的高效处理，算法能够在题目给定的约束范围内高效运行。

代码实现

以下是英文版的 C++ 实现：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>

using namespace std;

// Structure to represent an edge
struct Edge {
    int to;            // Target node
    int base_time;     // Base time to traverse this edge
    int base_cost;     // Base cost of this edge
    int base_resource; // Base resource consumption
    
    Edge(int t, int bt, int bc, int br) 
        : to(t), base_time(bt), base_cost(bc), base_resource(br) {}
};

// Structure to represent a state in priority queue
struct State {
    int node;     // Current node
    int time;     // Accumulated time
    int resource; // Accumulated resource consumption
    int cost;     // Accumulated cost
    
    State(int n, int t, int r, int c) 
        : node(n), time(t), resource(r), cost(c) {}
    
    // For priority queue (min-heap based on cost)
    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

// Calculate time-dependent cost 
// Higher cost during morning (7-9) and evening (17-19) rush hours
int get_time_dependent_cost(int base_cost, int current_time) {
    int hour = current_time % 24;
    if ((hour >= 7 && hour < 9) || (hour >= 17 && hour < 19)) {
        // 30% higher during rush hours
        return static_cast<int>(base_cost * 1.3);
    } else if (hour >= 0 && hour < 6) {
        // 20% lower during early morning
        return static_cast<int>(base_cost * 0.8);
    }
    return base_cost; // Normal hours
}

int main() {
    int n, m;               // Number of nodes and edges
    int S, T;               // Start and target nodes
    int T_max, R_max;       // Maximum allowed time and resource
    
    // Read input
    cin >> n >> m;
    cin >> S >> T >> T_max >> R_max;
    
    // Build adjacency list
    vector<vector<Edge>> adj(n + 1);  // Nodes are 1-indexed
    for (int i = 0; i < m; ++i) {
        int u, v, t, c, r;
        cin >> u >> v >> t >> c >> r;
        adj[u].emplace_back(v, t, c, r);
    }
    
    // DP table: dp[node][time][resource] = minimum cost
    // Using vector of vectors of vectors
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(
            T_max + 1, vector<int>(R_max + 1, INT_MAX)
        )
    );
    
    // Priority queue for modified Dijkstra's algorithm
    priority_queue<State, vector<State>, greater<State>> pq;
    
    // Initialize starting node
    dp[S][0][0] = 0;
    pq.emplace(S, 0, 0, 0);
    
    // Track the minimum cost to reach target
    int min_cost = INT_MAX;
    
    // Process states
    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();
        
        int u = current.node;
        int t = current.time;
        int r = current.resource;
        int c = current.cost;
        
        // If we've reached the target, update minimum cost
        if (u == T) {
            min_cost = min(min_cost, c);
            // Continue searching for possible lower costs
            continue;
        }
        
        // Skip if we've already found a better path to this state
        if (c > dp[u][t][r]) {
            continue;
        }
        
        // Explore all neighboring nodes
        for (const Edge& edge : adj[u]) {
            int v = edge.to;
            int cost = get_time_dependent_cost(edge.base_cost, t);
            
            // Option 1: Normal mode
            int new_time = t + edge.base_time;
            int new_resource = r + edge.base_resource;
            int new_cost = c + cost;
            
            if (new_time <= T_max && new_resource <= R_max) {
                if (new_cost < dp[v][new_time][new_resource]) {
                    dp[v][new_time][new_resource] = new_cost;
                    pq.emplace(v, new_time, new_resource, new_cost);
                }
            }
            
            // Option 2: High-speed mode (30% faster, 50% more resource)
            int high_speed_time = static_cast<int>(edge.base_time * 0.7);
            int high_speed_resource = static_cast<int>(edge.base_resource * 1.5);
            
            new_time = t + high_speed_time;
            new_resource = r + high_speed_resource;
            new_cost = c + cost;  // Cost remains the same
            
            if (new_time <= T_max && new_resource <= R_max) {
                if (new_cost < dp[v][new_time][new_resource]) {
                    dp[v][new_time][new_resource] = new_cost;
                    pq.emplace(v, new_time, new_resource, new_cost);
                }
            }
        }
    }
    
    // Output the result
    if (min_cost == INT_MAX) {
        cout << -1 << endl;  // No valid path found
    } else {
        cout << min_cost << endl;
    }
    
    return 0;
}

代码解析

上述代码实现了针对问题的完整解决方案，主要包含以下几个关键部分：

1. 数据结构设计：

   • Edge结构体存储边的基本信息：目标节点、基础时间、基础费用和基础资源消耗
   • State结构体表示队列中的状态，包含当前节点、累计时间、累计资源和累计费用
   • 重载operator>使优先队列按费用升序排列（最小堆）

2. 时效性费用计算：

   • get_time_dependent_cost函数实现了随时间变化的费用计算
   • 模拟了早高峰 (7-9 点) 和晚高峰 (17-19 点) 费用上涨 30%，凌晨 (0-6 点) 费用下降 20% 的现实场景

3. 核心算法实现：

   • 使用三维 DP 数组dp[node][time][resource]记录到达节点的最小费用
   • 采用优先队列实现改进的 Dijkstra 算法，确保优先处理费用较低的状态
   • 对每条边考虑两种模式（普通模式和高速模式），分别计算并更新状态

4. 约束处理：

   • 严格检查新状态是否满足时间和资源约束
   • 对超出约束的状态进行剪枝，不加入队列

5. 结果处理：

   • 记录到达终点的最小费用
   • 若无法到达则输出 - 1

该算法通过综合考虑时间、费用和资源的多重约束，以及动态变化的费用模型，有效地解决了这个复杂的路径优化问题。算法的时间和空间复杂度虽然较高，但通过优先队列和状态剪枝，能够在题目给定的约束范围内高效运行。

扩展思考

这道题可以从以下几个方向进行扩展：

1. 引入随机事件（如交通拥堵、资源价格波动）增加问题的不确定性
2. 考虑多目标优化，如在费用和时间之间寻找帕累托最优解
3. 扩展为多源多汇问题，处理更复杂的物流网络

这些扩展将进一步提高问题的复杂度，更贴近实际应用场景，考察选手对算法的灵活运用能力。

通过本题的求解可以看出，现代算法竞赛越来越注重实际问题的建模与解决，要求选手不仅掌握基础算法，还要能够将其灵活应用于复杂场景，这对选手的综合能力提出了更高要求。