2024 年 NOI 最后一题题解
问题描述
2024 年 NOI 最后一题是一道结合图论与动态规划的综合性算法题,题目要求解决带有时效性和资源约束的路径优化问题。具体描述如下:
给定一个有向图 G (V, E),其中节点代表站点,边代表连接站点的路径。每条边具有三个属性:基础行驶时间 t、基础费用 c 和资源消耗 r。需要将一批重要物资从起点 S 运输到终点 T,要求满足以下约束:
- 总行驶时间不超过 T_max
- 总资源消耗不超过 R_max
- 每条边的实际费用会随出发时间变化(模拟高峰期价格波动)
此外,每条边可以选择使用 "高速模式":消耗额外 50% 的资源,减少 30% 的行驶时间,费用保持不变。请设计算法找到满足所有约束条件的最小总费用路径。
问题分析
这道题是经典最短路径问题的扩展,融合了多重约束和决策选择,主要挑战包括:
- 三重约束:需要同时考虑时间、费用和资源三个维度
- 时效性:边的费用随出发时间动态变化
- 决策点:对每条边需要选择是否使用高速模式
- 多目标优化:在满足约束条件下最小化总费用
问题可以转化为带约束的多维度最优化问题,需要使用扩展的最短路径算法结合动态规划思想来解决。
算法设计
我们采用改进的 Dijkstra 算法,结合三维动态规划来处理多重约束:
- 状态表示:定义 dp [u][t][r] 为到达节点 u 时,累计时间为 t 且累计资源消耗为 r 的最小费用
- 状态转移:对于每个状态 (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)
- 约束条件:t' ≤ T_max 且 r' ≤ R_max
- 优先级队列:按费用排序,优先处理费用较低的状态
实现细节
- 三维 DP 数组:由于时间和资源可能较大,需要合理设置精度和范围
- 费用函数:实现随时间变化的费用计算,题目规定为工作日早晚高峰模式
- 状态压缩:对于相同节点、时间和资源消耗,只保留最小费用状态
- 决策处理:对每条边都考虑两种模式,分别计算并更新状态
- 边界条件:起点初始状态设置和终点状态的筛选
复杂度分析
- 时间复杂度: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 nodeint base_time; // Base time to traverse this edgeint base_cost; // Base cost of this edgeint base_resource; // Base resource consumptionEdge(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 nodeint time; // Accumulated timeint resource; // Accumulated resource consumptionint cost; // Accumulated costState(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 hoursreturn static_cast<int>(base_cost * 1.3);} else if (hour >= 0 && hour < 6) {// 20% lower during early morningreturn static_cast<int>(base_cost * 0.8);}return base_cost; // Normal hours
}int main() {int n, m; // Number of nodes and edgesint S, T; // Start and target nodesint T_max, R_max; // Maximum allowed time and resource// Read inputcin >> n >> m;cin >> S >> T >> T_max >> R_max;// Build adjacency listvector<vector<Edge>> adj(n + 1); // Nodes are 1-indexedfor (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 vectorsvector<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 algorithmpriority_queue<State, vector<State>, greater<State>> pq;// Initialize starting nodedp[S][0][0] = 0;pq.emplace(S, 0, 0, 0);// Track the minimum cost to reach targetint min_cost = INT_MAX;// Process stateswhile (!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 costif (u == T) {min_cost = min(min_cost, c);// Continue searching for possible lower costscontinue;}// Skip if we've already found a better path to this stateif (c > dp[u][t][r]) {continue;}// Explore all neighboring nodesfor (const Edge& edge : adj[u]) {int v = edge.to;int cost = get_time_dependent_cost(edge.base_cost, t);// Option 1: Normal modeint 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 sameif (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 resultif (min_cost == INT_MAX) {cout << -1 << endl; // No valid path found} else {cout << min_cost << endl;}return 0;
}
代码解析
上述代码实现了针对问题的完整解决方案,主要包含以下几个关键部分:
数据结构设计:
Edge
结构体存储边的基本信息:目标节点、基础时间、基础费用和基础资源消耗State
结构体表示队列中的状态,包含当前节点、累计时间、累计资源和累计费用- 重载
operator>
使优先队列按费用升序排列(最小堆)
时效性费用计算:
get_time_dependent_cost
函数实现了随时间变化的费用计算- 模拟了早高峰 (7-9 点) 和晚高峰 (17-19 点) 费用上涨 30%,凌晨 (0-6 点) 费用下降 20% 的现实场景
核心算法实现:
- 使用三维 DP 数组
dp[node][time][resource]
记录到达节点的最小费用 - 采用优先队列实现改进的 Dijkstra 算法,确保优先处理费用较低的状态
- 对每条边考虑两种模式(普通模式和高速模式),分别计算并更新状态
- 使用三维 DP 数组
约束处理:
- 严格检查新状态是否满足时间和资源约束
- 对超出约束的状态进行剪枝,不加入队列
结果处理:
- 记录到达终点的最小费用
- 若无法到达则输出 - 1
该算法通过综合考虑时间、费用和资源的多重约束,以及动态变化的费用模型,有效地解决了这个复杂的路径优化问题。算法的时间和空间复杂度虽然较高,但通过优先队列和状态剪枝,能够在题目给定的约束范围内高效运行。
扩展思考
这道题可以从以下几个方向进行扩展:
- 引入随机事件(如交通拥堵、资源价格波动)增加问题的不确定性
- 考虑多目标优化,如在费用和时间之间寻找帕累托最优解
- 扩展为多源多汇问题,处理更复杂的物流网络
这些扩展将进一步提高问题的复杂度,更贴近实际应用场景,考察选手对算法的灵活运用能力。
通过本题的求解可以看出,现代算法竞赛越来越注重实际问题的建模与解决,要求选手不仅掌握基础算法,还要能够将其灵活应用于复杂场景,这对选手的综合能力提出了更高要求。