2020 年 NOI 最后一題題解

問題描述

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 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 最后一題的完整解決方案，主要包含以下核心部分：

數據結構設計：
- Edge結構體存儲邊的行駛時間、成本和每日最大通行量
- Node結構體記錄節點的風險等級和防疫檢查時間
- State結構體表示優先隊列中的狀態，包含當前節點、天數、時刻和累計成本
- DPState結構體存儲動態規劃狀態信息，包括成本、前驅節點和到達方式
核心算法實現：
- 采用改進的 Dijkstra 算法，使用優先級隊列按成本、天數和時刻排序處理狀態
- 三維 DP 數組dp[node][day][hour]跟蹤到達節點的最優狀態
- 實現兩種狀態轉移：在當前節點停留，或通過邊前往相鄰節點
約束處理機制：
- 宵禁檢查：確保僅在 6-24 點使用邊進行運輸
- 容量管理：通過edge_usage數組跟蹤每條邊每天的使用次數
- 風險隔離：到達節點后自動計算并累加檢查時間和隔離時間（風險等級 ×2）
- 時間控制：嚴格限制總天數不超過 D_max
時間計算：
- add_time輔助函數處理時間累加和跨天計算
- 將時間分解為 "天數 + 時刻" 的組合形式，方便處理周期性約束
路徑重構與結果輸出：
- 通過前驅指針重構完整路徑
- 輸出最小成本、到達天數、時刻和完整路徑
- 若不存在滿足約束的路徑，輸出 - 1