问题描述
2020 年 NOI 最后一题是一道结合图论、动态规划与状态压缩的综合性算法题，题目围绕 "疫情期间的物资配送" 展开，具体要求如下：
给定一个有向图 G (V, E)，其中节点代表城市，边代表连接城市的道路。每个节点有两个属性：风险等级 l（0-5）和防疫检查时间 t。每条边有三个属性：行驶时间 d、基础成本 c 和最大每日通行量 k。
需要将一批应急物资从起点 S 运往终点 T，满足以下约束：
- 每日 0 点至 6 点为宵禁时间，禁止通行（边无法使用）
- 经过风险等级为 l 的节点需要额外隔离时间 l×2 小时
- 每条边每天的使用次数不能超过其最大通行量 k
- 总运输时间不得超过 D 天（按自然日计算）
请设计算法找到满足所有约束条件的最小成本运输方案，若存在多条路径则选择总运输时间最短的方案。
问题分析
本题的核心挑战在于时间与空间约束的复杂交互，传统路径算法需要进行针对性扩展：
- 时间周期性约束：宵禁制度引入了以天为周期的时间限制，影响边的可用性
- 节点风险成本：不同风险等级的节点会带来额外隔离时间，增加了状态维度
- 资源容量限制：边的每日通行量限制要求跟踪时间与使用次数的关系
- 多目标优化：首要目标是最小化成本，次要目标是缩短运输时间
问题可转化为带周期性时间约束和容量限制的最小成本路径问题，需要通过时间扩展网络来建模周期性约束。
算法设计
我们采用基于时间扩展网络的改进 Dijkstra 算法，结合动态规划处理周期性约束：
状态表示：定义 dp [u][d][t] 为第 d 天的 t 时刻到达节点 u 时的最小成本，其中：
- u 为当前节点
- d 为当前天数（从 0 开始）
- t 为当天时刻（0-23 小时）
状态转移：对于每个状态 (u, d, t)，考虑两种决策：
- 在节点停留：停留 Δt 时间后的新状态为 (u, d', t')，其中 d' 和 t' 根据跨天情况计算
- 前往相邻节点：使用边 (u, v)，需检查是否在宵禁时间，计算到达 v 的天数和时刻，更新成本
约束处理：
- 宵禁检查：边只能在 6-24 点使用（非宵禁时段）
- 容量限制：每条边按天跟踪使用次数，不超过最大通行量 k
- 风险隔离：到达节点 v 后需增加 l_v×2 小时的隔离时间
- 时间上限：总天数 d 不得超过 D
优先级队列：按成本排序，成本相同则按总时间（天数 + 时刻）排序
实现细节
- 时间建模：将时间分解为 "天数 + 时刻" 的组合形式，方便处理跨天和周期性约束
- 状态剪枝：对于相同节点、天数和时刻，仅保留最小成本状态
- 容量跟踪：使用三维数组 count [u][v][d] 记录边 (u, v) 在第 d 天的使用次数
- 隔离处理：到达节点后立即计算并累加隔离时间，更新状态时间
- 路径重构：通过前驱指针记录每个状态的来源，包括使用的边和停留决策
复杂度分析
- 时间复杂度：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 node
int duration; // Travel time in hours
int cost; // Transportation cost
int capacity; // Maximum daily capacity
Edge(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 node
int day; // Current day
int hour; // Current hour (0-23)
int cost; // Accumulated cost
State(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 state
int prev_node; // Previous node
int prev_day; // Previous day
int prev_hour; // Previous hour
int 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 edges
int S, T, D_max; // Start node, target node, maximum allowed days
// Read input
cin >> n >> m;
cin >> S >> T >> D_max;
// Initialize nodes
vector<Node> nodes(n + 1); // 1-indexed
for (int i = 1; i <= n; ++i) {
cin >> nodes[i].risk_level >> nodes[i].check_time;
}
// Read edges
vector<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 count
for (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 state
vector<vector<vector<DPState>>> dp(
n + 1, vector<vector<DPState>>(
MAX_DAYS, vector<DPState>(HOURS_PER_DAY)
)
);
// Priority queue for modified Dijkstra's algorithm
priority_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 curfew
dp[S][0][start_hour].cost = 0;
pq.emplace(S, 0, start_hour, 0);
// Track best solution
int best_cost = INF_COST;
int best_day = -1;
int best_hour = -1;
// Process states
while (!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 days
if (day >= D_max) {
continue;
}
// Skip if we've found a better state
if (cost > dp[u][day][hour].cost) {
continue;
}
// Check if we've reached target
if (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 staying
pq.emplace(u, new_day, new_hour, cost);
}
// Option 2: Travel to adjacent nodes via edges
for (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 time
int arrival_day = day;
int arrival_hour = hour + travel_time;
// Handle day transitions
while (arrival_hour >= HOURS_PER_DAY) {
arrival_hour -= HOURS_PER_DAY;
arrival_day++;
}
// Check if we exceed maximum days
if (arrival_day >= D_max) {
continue;
}
// Check edge capacity for current day
if (edge_usage[u][v][day] >= edge.capacity) {
continue;
}
// Calculate total time including check and quarantine at destination
int 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 cost
int new_cost = cost + edge_cost;
// Update edge usage (temporarily)
edge_usage[u][v][day]++;
// Update state if this path is better
if (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 usage
edge_usage[u][v][day]--;
}
}
}
// Check if solution exists
if (best_cost == INF_COST) {
cout << -1 << endl;
return 0;
}
// Reconstruct path
vector<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 results
cout << 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 最后一题的完整解决方案，主要包含以下核心部分：
数据结构设计：
Edge结构体存储边的行驶时间、成本和每日最大通行量Node结构体记录节点的风险等级和防疫检查时间State结构体表示优先队列中的状态，包含当前节点、天数、时刻和累计成本DPState结构体存储动态规划状态信息，包括成本、前驱节点和到达方式
核心算法实现：
- 采用改进的 Dijkstra 算法，使用优先级队列按成本、天数和时刻排序处理状态
- 三维 DP 数组
dp[node][day][hour]跟踪到达节点的最优状态 - 实现两种状态转移：在当前节点停留，或通过边前往相邻节点
约束处理机制：
- 宵禁检查：确保仅在 6-24 点使用边进行运输
- 容量管理：通过
edge_usage数组跟踪每条边每天的使用次数 - 风险隔离：到达节点后自动计算并累加检查时间和隔离时间（风险等级 ×2）
- 时间控制：严格限制总天数不超过 D_max
时间计算：
add_time辅助函数处理时间累加和跨天计算- 将时间分解为 "天数 + 时刻" 的组合形式，方便处理周期性约束
路径重构与结果输出：
- 通过前驱指针重构完整路径
- 输出最小成本、到达天数、时刻和完整路径
- 若不存在满足约束的路径，输出 - 1
该算法通过时间扩展网络模型成功处理了周期性宵禁约束，结合动态规划跟踪节点风险带来的额外时间成本，在满足所有防疫和通行约束的前提下找到了最小成本运输方案。
扩展思考
本题可以从以下几个方向进行扩展：
- 引入动态风险等级，节点风险随时间变化，增加状态动态性
- 考虑物资保质期，要求在特定时间前送达，增加时间约束复杂度
- 扩展为多批次运输，考虑批次间的资源竞争和协调
- 加入随机事件（如道路临时封闭、风险等级突变），设计鲁棒性方案
这些扩展更贴近疫情期间复杂多变的实际运输场景，对算法的适应性和前瞻性提出了更高要求。
通过本题的求解可以看出，NOI 题目注重考察选手将实际问题抽象为算法模型的能力，尤其是处理多重约束和周期性条件的能力，这要求选手不仅掌握基础算法，还要具备灵活的问题建模能力。