当前位置: 首页 > news >正文

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 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;
}
代码解析

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

  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. 扩展为多源多汇问题,处理更复杂的物流网络

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

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

http://www.xdnf.cn/news/1214119.html

相关文章:

  • 算法精讲:二分查找(二)—— 变形技巧
  • 【Excel】制作双重饼图
  • 关于windows虚拟机无法联网问题
  • VMware16安装Ubuntu-22.04.X版本(并使用桥接模式实现局域网下使用ssh远程操作Ubuntu系统)
  • 【硬件-笔试面试题】硬件/电子工程师,笔试面试题-51,(知识点:stm32,GPIO基础知识)
  • C++菱形虚拟继承:解开钻石继承的魔咒
  • 简单线性回归模型原理推导(最小二乘法)和案例解析
  • 线性回归的应用
  • 明智运用C++异常规范(Exception Specifications)
  • 爬虫验证码处理:ddddocr 的详细使用(通用验证码识别OCR pypi版)
  • 架构实战——架构重构内功心法第一式(有的放矢)
  • 地图可视化实践录:显示高德地图和百度地图
  • Linux 进程管理与计划任务详解
  • 关于神经网络CNN的搭建过程以及图像卷积的实现过程学习
  • Mac下的Homebrew
  • 如何不让android studio自动换行
  • cpp c++面试常考算法题汇总
  • 高防CDN与高防IP的选择
  • 【ip】IP地址能否直接填写255?
  • SpringBoot升级2.5.3 2.6.8
  • gtest框架的安装与使用
  • 基于成像空间转录组技术的肿瘤亚克隆CNV原位推断方法
  • android-PMS-创建新用户流程
  • VUE -- 基础知识讲解(三)
  • 记录Linux下ping外网失败的问题
  • 时序数据库厂商 TDengine 发布 AI 原生的工业数据管理平台 IDMP,“无问智推”改变数据消费范式
  • 问题1:uniapp在pages样式穿刺没有问题,在components组件中样式穿刺小程序不起效果
  • Django常见模型字段
  • 一篇文章读懂麦科信CP3008系列高频交直流电流探头
  • 基于数字信息化的全面研发项目管理︱裕太微电子股份有限公司研发项目管理部负责人唐超