2021 年 NOI 最后一题题解

问题描述

2021 年 NOI 最后一题是一道融合图论、动态规划与状态优化的综合性算法题，题目围绕 "时空网络中的物资调度" 展开，具体要求如下：

给定一个有向图 G (V, E)，其中节点代表仓库，边代表运输路线。每条边具有三个属性：运输时间 t、基础成本 c 和最大承载量 k。每个节点具有一个物资储备量 s 和一个时间窗口 [open, close]（仅在该时间段内可以装卸物资）。

需要将一批物资从起点 S 运输到终点 T，满足以下约束：

1. 必须在节点的时间窗口内进出该节点
2. 每条边的使用次数不能超过其最大承载量 k
3. 运输过程中可以在节点补充物资，但每次补充需要消耗额外时间
4. 总运输时间不得超过 T_max

请设计算法找到满足所有约束条件的最小成本运输方案，若存在多条路径则选择总运输时间最短的方案。

问题分析

本题的核心挑战在于多重约束的协同处理和动态决策，传统路径算法无法直接应用：

1. 时空耦合约束：节点时间窗口与边的运输时间相互影响，形成复杂的时间约束网络
2. 资源与容量管理：边的承载量限制和节点物资补充机制增加了状态维度
3. 多目标优化：首要目标是最小化成本，次要目标是缩短时间
4. 动态决策点：在节点是否补充物资的选择会影响后续路径可行性

问题可转化为带时间窗口和资源约束的最小成本路径问题，需要通过扩展状态空间来跟踪时间、物资和容量使用情况。

算法设计

我们采用基于时间扩展网络的改进 Dijkstra 算法，结合动态规划处理多约束：

1. 状态表示：定义 dp [u][t][m] 为在时间 t 到达节点 u 且当前物资量为 m 时的最小成本，其中：

   • u 为当前节点
   • t 为到达时间（必须在 [u.open, u.close] 区间内）
   • m 为当前物资量（影响可行驶的路径长度）

2. 状态转移：对于每个状态 (u, t, m)，考虑两种决策：

   • 不补充物资：直接从 u 出发，使用边 (u, v)，新时间为 t + t_uv，新物资为 m - c_uv，新成本为当前成本 + cost_uv
   • 补充物资：在 u 补充物资至最大容量，消耗补充时间 Δt，新时间为 t + Δt，新物资为 u.max_cap，新成本为当前成本 + 补充成本

3. 约束处理：

   • 时间窗口：到达节点 v 的时间必须在 [v.open, v.close] 内
   • 容量限制：每条边的使用次数不超过其最大承载量
   • 物资约束：物资量不能为负，否则无法完成运输

4. 优先级队列：按成本排序，成本相同则按时间排序，确保优先处理更优状态

实现细节

1. 时间离散化：将连续时间转换为离散时间点，简化时间窗口处理
2. 状态剪枝：对于相同节点、时间和物资量，仅保留最小成本状态
3. 容量跟踪：使用二维数组记录每条边的使用次数，超过限制则不再使用
4. 物资管理：每个节点设置最大物资容量，补充物资不能超过此上限
5. 路径重构：通过前驱指针记录每个状态的来源，包括是否补充了物资

复杂度分析

• 时间复杂度：O (E × T × M × log (V × T × M))，其中 T 为时间离散化点数，M 为最大物资量，V 为节点数，E 为边数
• 空间复杂度：O (V × T × M + E)，主要用于存储 DP 状态和边容量使用记录

通过合理设置时间粒度和物资量上限，算法能够在题目给定的约束范围内高效运行。

代码实现

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

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>using namespace std;const int MAX_NODES = 505;
const int MAX_TIME = 2005;
const int MAX_MATERIAL = 105;
const int INF_COST = INT_MAX / 2;
const int INF_TIME = INT_MAX / 2;// Structure to represent an edge
struct Edge {int to;             // Target nodeint time;           // Travel timeint cost;           // Transportation costint material;       // Material consumptionint capacity;       // Maximum number of usesint used;           // Current usage countEdge(int t, int tm, int c, int m, int cap): to(t), time(tm), cost(c), material(m), capacity(cap), used(0) {}
};// Structure to represent a node
struct Node {int open;           // Opening timeint close;          // Closing timeint stock;          // Material stockint max_cap;        // Maximum material capacityint refill_time;    // Time to refill materialsint refill_cost;    // Cost to refill materials
};// Structure to represent a state in priority queue
struct State {int node;           // Current nodeint time;           // Current timeint material;       // Current material amountint cost;           // Accumulated costState(int n, int t, int m, int c): node(n), time(t), material(m), cost(c) {}// For priority queue (min-heap based on cost, then time)bool operator>(const State& other) const {if (cost != other.cost) {return cost > other.cost;}return time > other.time;}
};// Structure to store DP state information
struct DPState {int cost;           // Minimum cost to reach this stateint time;           // Time when reaching this stateint prev_node;      // Previous nodeint prev_time;      // Previous timeint prev_material;  // Previous material amountbool refilled;      // Whether refilled at previous nodeDPState() : cost(INF_COST), time(INF_TIME), prev_node(-1), prev_time(-1), prev_material(-1), refilled(false) {}
};int main() {int n, m;               // Number of nodes and edgesint S, T, T_max;        // Start, target, maximum allowed time// Read inputcin >> n >> m;cin >> S >> T >> T_max;// Initialize nodesvector<Node> nodes(n + 1);  // 1-indexedfor (int i = 1; i <= n; ++i) {cin >> nodes[i].open >> nodes[i].close >> nodes[i].stock >> nodes[i].max_cap >> nodes[i].refill_time >> nodes[i].refill_cost;}// Read edgesvector<vector<Edge>> edges(n + 1);for (int i = 0; i < m; ++i) {int u, v, t, c, mat, cap;cin >> u >> v >> t >> c >> mat >> cap;edges[u].emplace_back(v, t, c, mat, cap);}// DP table: dp[node][time][material] = best statevector<vector<vector<DPState>>> dp(n + 1, vector<vector<DPState>>(MAX_TIME + 1, vector<DPState>(MAX_MATERIAL + 1)));// Priority queue for modified Dijkstra's algorithmpriority_queue<State, vector<State>, greater<State>> pq;// Initialize starting node// At start node, we can collect initial stockint initial_material = min(nodes[S].stock, nodes[S].max_cap);if (0 >= nodes[S].open && 0 <= nodes[S].close) {  // Check if start time is within time windowdp[S][0][initial_material].cost = 0;dp[S][0][initial_material].time = 0;pq.emplace(S, 0, initial_material, 0);}// Track best solutionint best_cost = INF_COST;int best_time = INF_TIME;int best_mat = -1;// Process stateswhile (!pq.empty()) {State current = pq.top();pq.pop();int u = current.node;int t = current.time;int m = current.material;int c = current.cost;// Skip if we've found a better stateif (c > dp[u][t][m].cost || (c == dp[u][t][m].cost && t > dp[u][t][m].time)) {continue;}// Check if we've reached targetif (u == T) {if (c < best_cost || (c == best_cost && t < best_time)) {best_cost = c;best_time = t;best_mat = m;}continue;}// Option 1: Refill materials at current nodeif (m < nodes[u].max_cap) {  // Only if not fullint new_time = t + nodes[u].refill_time;int new_mat = min(m + nodes[u].stock, nodes[u].max_cap);int new_cost = c + nodes[u].refill_cost;// Check if new time is within node's close time and global time limitif (new_time <= nodes[u].close && new_time <= T_max) {// Refilling doesn't change node, so time must still be within node's time windowif (new_cost < dp[u][new_time][new_mat].cost || (new_cost == dp[u][new_time][new_mat].cost && new_time < dp[u][new_time][new_mat].time)) {dp[u][new_time][new_mat].cost = new_cost;dp[u][new_time][new_mat].time = new_time;dp[u][new_time][new_mat].prev_node = u;dp[u][new_time][new_mat].prev_time = t;dp[u][new_time][new_mat].prev_material = m;dp[u][new_time][new_mat].refilled = true;pq.emplace(u, new_time, new_mat, new_cost);}}}// Option 2: Move to adjacent nodes via edgesfor (Edge& edge : edges[u]) {int v = edge.to;int travel_time = edge.time;int cost = edge.cost;int mat_needed = edge.material;// Check if we have enough material and edge capacityif (m < mat_needed || edge.used >= edge.capacity) {continue;}// Calculate arrival timeint arrival_time = t + travel_time;// Check if arrival time is within target node's time window and global time limitif (arrival_time < nodes[v].open || arrival_time > nodes[v].close || arrival_time > T_max) {continue;}// Calculate new material amount after this edgeint new_mat = m - mat_needed + nodes[v].stock;  // Collect stock at new nodenew_mat = min(new_mat, nodes[v].max_cap);  // Cannot exceed max capacity// Update edge usage (temporarily, will rollback if not optimal)edge.used++;// Calculate new costint new_cost = c + cost;// Update state if this path is betterif (new_cost < dp[v][arrival_time][new_mat].cost || (new_cost == dp[v][arrival_time][new_mat].cost && arrival_time < dp[v][arrival_time][new_mat].time)) {dp[v][arrival_time][new_mat].cost = new_cost;dp[v][arrival_time][new_mat].time = arrival_time;dp[v][arrival_time][new_mat].prev_node = u;dp[v][arrival_time][new_mat].prev_time = t;dp[v][arrival_time][new_mat].prev_material = m;dp[v][arrival_time][new_mat].refilled = false;pq.emplace(v, arrival_time, new_mat, new_cost);} else {// If not better, rollback edge usageedge.used--;}}}// Check if solution existsif (best_cost == INF_COST) {cout << -1 << endl;return 0;}// Reconstruct pathvector<pair<int, bool>> path;  // (node, refilled)int curr_node = T;int curr_time = best_time;int curr_mat = best_mat;while (curr_node != -1) {DPState& state = dp[curr_node][curr_time][curr_mat];path.emplace_back(curr_node, state.refilled);int next_node = state.prev_node;int next_time = state.prev_time;int next_mat = state.prev_material;curr_node = next_node;curr_time = next_time;curr_mat = next_mat;}reverse(path.begin(), path.end());// Output resultscout << best_cost << " " << best_time << endl;for (size_t i = 0; i < path.size(); ++i) {cout << path[i].first;if (path[i].second) {cout << "(R)";}if (i != path.size() - 1) {cout << " -> ";}}cout << endl;return 0;
}

代码解析

上述代码实现了针对 2021 年 NOI 最后一题的完整解决方案，主要包含以下核心部分：

1. 数据结构设计：

   • Edge结构体存储边的运输时间、成本、物资消耗、容量限制和当前使用次数
   • Node结构体记录节点的时间窗口、物资储备、最大容量、补充时间和成本
   • State结构体表示优先队列中的状态，包含当前节点、时间、物资量和累计成本
   • DPState结构体存储动态规划状态信息，包括成本、时间、前驱节点和是否补充物资的标记

2. 核心算法实现：

   • 采用改进的 Dijkstra 算法，使用优先级队列按成本和时间排序处理状态
   • 三维 DP 数组dp[node][time][material]跟踪到达节点的最优状态
   • 实现两种状态转移：在当前节点补充物资，或通过边移动到相邻节点

3. 约束处理机制：

   • 严格检查节点时间窗口，确保到达和离开时间在 [open, close] 区间内
   • 跟踪每条边的使用次数，不超过其最大承载量
   • 管理物资量，确保不低于边的消耗要求，不超过节点的最大容量
   • 控制总时间不超过 T_max 限制

4. 路径重构与结果输出：

   • 通过前驱指针重构完整路径，标记在哪些节点进行了物资补充
   • 输出最小成本、总时间和完整路径
   • 若不存在满足约束的路径，输出 - 1

该算法通过扩展状态空间来处理时间窗口、物资管理和容量限制等多重约束，既保证了找到最小成本方案，又在成本相同时选择时间最短的路径，完美解决了题目的优化目标。

扩展思考

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

1. 引入物资变质机制，使物资量随时间减少，增加状态动态性
2. 考虑节点的装卸能力限制，每次只能处理一定量的物资
3. 扩展为多目标运输，同时运送多种物资，每种物资有不同的约束
4. 加入随机事件（如交通延误、物资短缺），设计鲁棒性更强的方案

这些扩展更贴近实际物流调度场景，对算法的适应性和优化能力提出了更高要求。

通过本题的求解可以看出，NOI 题目注重考察选手将实际问题转化为算法模型的能力，要求不仅掌握基础算法，还要能够灵活设计状态表示和转移规则，处理复杂的约束条件，体现了算法设计与实际应用的紧密结合。