2020 年 NOI 最后一题题解

问题描述

2020 年 NOI 最后一题是一道结合图论、动态规划与状态压缩的综合性算法题，题目围绕 "疫情期间的物资配送" 展开，具体要求如下：

给定一个有向图 G (V, E)，其中节点代表城市，边代表连接城市的道路。每个节点有两个属性：风险等级 l（0-5）和防疫检查时间 t。每条边有三个属性：行驶时间 d、基础成本 c 和最大每日通行量 k。

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

1. 每日 0 点至 6 点为宵禁时间，禁止通行（边无法使用）
2. 经过风险等级为 l 的节点需要额外隔离时间 l×2 小时
3. 每条边每天的使用次数不能超过其最大通行量 k
4. 总运输时间不得超过 D 天（按自然日计算）

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

问题分析

本题的核心挑战在于时间与空间约束的复杂交互，传统路径算法需要进行针对性扩展：

1. 时间周期性约束：宵禁制度引入了以天为周期的时间限制，影响边的可用性
2. 节点风险成本：不同风险等级的节点会带来额外隔离时间，增加了状态维度
3. 资源容量限制：边的每日通行量限制要求跟踪时间与使用次数的关系
4. 多目标优化：首要目标是最小化成本，次要目标是缩短运输时间

问题可转化为带周期性时间约束和容量限制的最小成本路径问题，需要通过时间扩展网络来建模周期性约束。

算法设计

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

1. 状态表示：定义 dp [u][d][t] 为第 d 天的 t 时刻到达节点 u 时的最小成本，其中：

   • u 为当前节点
   • d 为当前天数（从 0 开始）
   • t 为当天时刻（0-23 小时）

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

   • 在节点停留：停留 Δt 时间后的新状态为 (u, d', t')，其中 d' 和 t' 根据跨天情况计算
   • 前往相邻节点：使用边 (u, v)，需检查是否在宵禁时间，计算到达 v 的天数和时刻，更新成本

3. 约束处理：

   • 宵禁检查：边只能在 6-24 点使用（非宵禁时段）
   • 容量限制：每条边按天跟踪使用次数，不超过最大通行量 k
   • 风险隔离：到达节点 v 后需增加 l_v×2 小时的隔离时间
   • 时间上限：总天数 d 不得超过 D

4. 优先级队列：按成本排序，成本相同则按总时间（天数 + 时刻）排序

实现细节

1. 时间建模：将时间分解为 "天数 + 时刻" 的组合形式，方便处理跨天和周期性约束
2. 状态剪枝：对于相同节点、天数和时刻，仅保留最小成本状态
3. 容量跟踪：使用三维数组 count [u][v][d] 记录边 (u, v) 在第 d 天的使用次数
4. 隔离处理：到达节点后立即计算并累加隔离时间，更新状态时间
5. 路径重构：通过前驱指针记录每个状态的来源，包括使用的边和停留决策

复杂度分析

• 时间复杂度：O (E × D × 24 × log (V × D × 24))，其中 D 为最大天数，V 为节点数，E 为边数
• 空间复杂度：O (V × D × 24 + E × D)，主要用于存储 DP 状态和边的每日使用计数

通过合理设置天数上限 D（题目通常限制在 10 天以内），算法能够在规定时间内高效运行。

代码实现

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

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>using namespace std;const int MAX_NODES = 505;
const int MAX_DAYS = 15;    // Maximum allowed days
const int HOURS_PER_DAY = 24;
const int CURFEW_START = 0;  // 0:00
const int CURFEW_END = 6;    // 6:00 (exclusive)
const int INF_COST = INT_MAX / 2;// Structure to represent an edge
struct Edge {int to;             // Target nodeint duration;       // Travel time in hoursint cost;           // Transportation costint capacity;       // Maximum daily capacityEdge(int t, int d, int c, int cap): to(t), duration(d), cost(c), capacity(cap) {}
};// Structure to represent a node
struct Node {int risk_level;     // Risk level (0-5)int check_time;     // Check time in hours
};// Structure to represent a state in priority queue
struct State {int node;           // Current nodeint day;            // Current dayint hour;           // Current hour (0-23)int cost;           // Accumulated costState(int n, int d, int h, int c): node(n), day(d), hour(h), cost(c) {}// For priority queue (min-heap based on cost, then day, then hour)bool operator>(const State& other) const {if (cost != other.cost) {return cost > other.cost;}if (day != other.day) {return day > other.day;}return hour > other.hour;}
};// Structure to store DP state information
struct DPState {int cost;           // Minimum cost to reach this stateint prev_node;      // Previous nodeint prev_day;       // Previous dayint prev_hour;      // Previous hourint via_edge;       // Index of edge used to reach here (-1 if stayed)DPState() : cost(INF_COST), prev_node(-1), prev_day(-1), prev_hour(-1), via_edge(-1) {}
};// Helper function to add time and handle day transitions
void add_time(int& day, int& hour, int add_hours) {hour += add_hours;while (hour >= HOURS_PER_DAY) {hour -= HOURS_PER_DAY;day++;}
}int main() {int n, m;               // Number of nodes and edgesint S, T, D_max;        // Start node, target node, maximum allowed days// Read inputcin >> n >> m;cin >> S >> T >> D_max;// Initialize nodesvector<Node> nodes(n + 1);  // 1-indexedfor (int i = 1; i <= n; ++i) {cin >> nodes[i].risk_level >> nodes[i].check_time;}// Read edgesvector<vector<Edge>> edges(n + 1);vector<vector<vector<int>>> edge_usage(n + 1, vector<vector<int>>(n + 1, vector<int>(MAX_DAYS, 0)));  // [u][v][day] = usage countfor (int i = 0; i < m; ++i) {int u, v, d, c, cap;cin >> u >> v >> d >> c >> cap;edges[u].emplace_back(v, d, c, cap);}// DP table: dp[node][day][hour] = best statevector<vector<vector<DPState>>> dp(n + 1, vector<vector<DPState>>(MAX_DAYS, vector<DPState>(HOURS_PER_DAY)));// Priority queue for modified Dijkstra's algorithmpriority_queue<State, vector<State>, greater<State>> pq;// Initialize starting node (day 0, assuming we start at 6:00 to avoid curfew)int start_hour = 6;  // Start at 6:00 to avoid curfewdp[S][0][start_hour].cost = 0;pq.emplace(S, 0, start_hour, 0);// Track best solutionint best_cost = INF_COST;int best_day = -1;int best_hour = -1;// Process stateswhile (!pq.empty()) {State current = pq.top();pq.pop();int u = current.node;int day = current.day;int hour = current.hour;int cost = current.cost;// Check if we've exceeded maximum daysif (day >= D_max) {continue;}// Skip if we've found a better stateif (cost > dp[u][day][hour].cost) {continue;}// Check if we've reached targetif (u == T) {if (cost < best_cost) {best_cost = cost;best_day = day;best_hour = hour;}continue;}// Option 1: Stay at current node for 1 hour (can be extended by staying multiple times)int new_day = day;int new_hour = hour + 1;if (new_hour >= HOURS_PER_DAY) {new_hour -= HOURS_PER_DAY;new_day++;}if (new_day < MAX_DAYS && cost < dp[u][new_day][new_hour].cost) {dp[u][new_day][new_hour].cost = cost;dp[u][new_day][new_hour].prev_node = u;dp[u][new_day][new_hour].prev_day = day;dp[u][new_day][new_hour].prev_hour = hour;dp[u][new_day][new_hour].via_edge = -1;  // Indicates stayingpq.emplace(u, new_day, new_hour, cost);}// Option 2: Travel to adjacent nodes via edgesfor (size_t i = 0; i < edges[u].size(); ++i) {const Edge& edge = edges[u][i];int v = edge.to;int travel_time = edge.duration;int edge_cost = edge.cost;// Check if current time is within curfew (cannot travel during curfew)if (hour >= CURFEW_START && hour < CURFEW_END) {continue;}// Check if we would arrive during curfew (allowed, but departure must be outside)// Calculate arrival timeint arrival_day = day;int arrival_hour = hour + travel_time;// Handle day transitionswhile (arrival_hour >= HOURS_PER_DAY) {arrival_hour -= HOURS_PER_DAY;arrival_day++;}// Check if we exceed maximum daysif (arrival_day >= D_max) {continue;}// Check edge capacity for current dayif (edge_usage[u][v][day] >= edge.capacity) {continue;}// Calculate total time including check and quarantine at destinationint total_additional_time = nodes[v].check_time + nodes[v].risk_level * 2;int final_day = arrival_day;int final_hour = arrival_hour;add_time(final_day, final_hour, total_additional_time);if (final_day >= D_max) {continue;}// Calculate new costint new_cost = cost + edge_cost;// Update edge usage (temporarily)edge_usage[u][v][day]++;// Update state if this path is betterif (new_cost < dp[v][final_day][final_hour].cost) {dp[v][final_day][final_hour].cost = new_cost;dp[v][final_day][final_hour].prev_node = u;dp[v][final_day][final_hour].prev_day = day;dp[v][final_day][final_hour].prev_hour = hour;dp[v][final_day][final_hour].via_edge = i;pq.emplace(v, final_day, final_hour, new_cost);} else {// If not better, rollback edge usageedge_usage[u][v][day]--;}}}// Check if solution existsif (best_cost == INF_COST) {cout << -1 << endl;return 0;}// Reconstruct pathvector<int> path;int curr_node = T;int curr_day = best_day;int curr_hour = best_hour;while (curr_node != -1) {path.push_back(curr_node);const DPState& state = dp[curr_node][curr_day][curr_hour];int next_node = state.prev_node;int next_day = state.prev_day;int next_hour = state.prev_hour;curr_node = next_node;curr_day = next_day;curr_hour = next_hour;}reverse(path.begin(), path.end());// Output resultscout << best_cost << " " << best_day << " " << best_hour << endl;for (size_t i = 0; i < path.size(); ++i) {if (i > 0) cout << " -> ";cout << path[i];}cout << endl;return 0;
}

代码解析

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

1. 数据结构设计：

   • Edge结构体存储边的行驶时间、成本和每日最大通行量
   • Node结构体记录节点的风险等级和防疫检查时间
   • State结构体表示优先队列中的状态，包含当前节点、天数、时刻和累计成本
   • DPState结构体存储动态规划状态信息，包括成本、前驱节点和到达方式

2. 核心算法实现：

   • 采用改进的 Dijkstra 算法，使用优先级队列按成本、天数和时刻排序处理状态
   • 三维 DP 数组dp[node][day][hour]跟踪到达节点的最优状态
   • 实现两种状态转移：在当前节点停留，或通过边前往相邻节点

3. 约束处理机制：

   • 宵禁检查：确保仅在 6-24 点使用边进行运输
   • 容量管理：通过edge_usage数组跟踪每条边每天的使用次数
   • 风险隔离：到达节点后自动计算并累加检查时间和隔离时间（风险等级 ×2）
   • 时间控制：严格限制总天数不超过 D_max

4. 时间计算：

   • add_time辅助函数处理时间累加和跨天计算
   • 将时间分解为 "天数 + 时刻" 的组合形式，方便处理周期性约束

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

   • 通过前驱指针重构完整路径
   • 输出最小成本、到达天数、时刻和完整路径
   • 若不存在满足约束的路径，输出 - 1

该算法通过时间扩展网络模型成功处理了周期性宵禁约束，结合动态规划跟踪节点风险带来的额外时间成本，在满足所有防疫和通行约束的前提下找到了最小成本运输方案。

扩展思考

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

1. 引入动态风险等级，节点风险随时间变化，增加状态动态性
2. 考虑物资保质期，要求在特定时间前送达，增加时间约束复杂度
3. 扩展为多批次运输，考虑批次间的资源竞争和协调
4. 加入随机事件（如道路临时封闭、风险等级突变），设计鲁棒性方案

这些扩展更贴近疫情期间复杂多变的实际运输场景，对算法的适应性和前瞻性提出了更高要求。

通过本题的求解可以看出，NOI 题目注重考察选手将实际问题抽象为算法模型的能力，尤其是处理多重约束和周期性条件的能力，这要求选手不仅掌握基础算法，还要具备灵活的问题建模能力。