php企业网站源码,微信小程序开发公司,番禺网站建设,wordpress简洁主题问题描述2020 年 NOI 最后一题是一道结合图论、动态规划与状态压缩的综合性算法题#xff0c;题目围绕 疫情期间的物资配送 展开#xff0c;具体要求如下#xff1a;给定一个有向图 G (V, E)#xff0c;其中节点代表城市#xff0c;边代表连接城市的道路。每个…问题描述2020 年 NOI 最后一题是一道结合图论、动态规划与状态压缩的综合性算法题题目围绕 疫情期间的物资配送 展开具体要求如下给定一个有向图 G (V, E)其中节点代表城市边代表连接城市的道路。每个节点有两个属性风险等级 l0-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 algorithmusing 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 nodesvectorNode nodes(n 1); // 1-indexedfor (int i 1; i n; i) {cin nodes[i].risk_level nodes[i].check_time;}// Read edgesvectorvectorEdge edges(n 1);vectorvectorvectorint edge_usage(n 1, vectorvectorint(n 1, vectorint(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 statevectorvectorvectorDPState dp(n 1, vectorvectorDPState(MAX_DAYS, vectorDPState(HOURS_PER_DAY)));// Priority queue for modified Dijkstras algorithmpriority_queueState, vectorState, greaterState 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 weve exceeded maximum daysif (day D_max) {continue;}// Skip if weve found a better stateif (cost dp[u][day][hour].cost) {continue;}// Check if weve 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 pathvectorint 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该算法通过时间扩展网络模型成功处理了周期性宵禁约束结合动态规划跟踪节点风险带来的额外时间成本在满足所有防疫和通行约束的前提下找到了最小成本运输方案。扩展思考本题可以从以下几个方向进行扩展引入动态风险等级节点风险随时间变化增加状态动态性考虑物资保质期要求在特定时间前送达增加时间约束复杂度扩展为多批次运输考虑批次间的资源竞争和协调加入随机事件如道路临时封闭、风险等级突变设计鲁棒性方案这些扩展更贴近疫情期间复杂多变的实际运输场景对算法的适应性和前瞻性提出了更高要求。通过本题的求解可以看出NOI 题目注重考察选手将实际问题抽象为算法模型的能力尤其是处理多重约束和周期性条件的能力这要求选手不仅掌握基础算法还要具备灵活的问题建模能力。
