2022 年 NOI 最后一题题解

问题描述

2022 年 NOI 最后一题是一道结合图论、动态规划和状态压缩的综合性算法题，题目围绕 "权限控制的城市网络" 展开，具体要求如下：

给定一个有向图 G (V, E)，其中节点代表城市，边代表城市间的道路。每个节点具有两个属性：资源值 r 和权限等级 l。每条边具有三个属性：通行时间 t、所需权限等级 req 和资源消耗 c。

要求从起点 S 出发，最终到达终点 T，满足以下约束：

1. 只有当当前权限等级≥边的所需权限等级 req 时，才能使用该边
2. 收集节点的资源值可以提升权限等级（权限等级与累计资源值正相关）
3. 总通行时间不超过 T_max

请设计算法找到满足约束条件的最短通行时间路径，若存在多条，则选择资源消耗最小的路径。

问题分析

本题的核心挑战在于权限等级与资源收集之间的动态关系，这使得传统的最短路径算法无法直接应用：

1. 状态依赖性：权限等级决定了可访问的边，而权限等级又取决于已收集的资源
2. 双重优化目标：首要目标是最小化通行时间，次要目标是最小化资源消耗
3. 动态约束：随着路径推进，可访问的边集可能发生变化（权限提升后可使用更高要求的边）

问题可以转化为带状态依赖约束的最短路径问题，需要通过扩展状态空间来跟踪权限等级的变化。

算法设计

我们采用改进的 Dijkstra 算法，通过扩展状态空间来处理权限等级的动态变化：

1. 状态表示：定义 dp [u][k] 为到达节点 u 时权限等级为 k 的最小通行时间，若时间相同则记录最小资源消耗
2. 权限等级计算：权限等级 k 与累计资源 r 的关系为 k = floor (r / R)，其中 R 为题目给定的资源阈值
3. 状态转移：对于每个状态 (u, k)，考虑所有从 u 出发且 req ≤ k 的边 (u, v)：
   • 新时间 = dp [u][k].time + t_uv
   • 新资源 = 累计资源 + r_v（节点 v 的资源值）- c_uv（边的资源消耗）
   • 新权限等级 k' = floor (新资源 / R)
   • 若新时间 <dp [v][k'].time，或时间相等但资源消耗更小，则更新状态
4. 优先级队列：按通行时间排序，时间相同则按资源消耗排序

实现细节

1. 状态初始化：起点 S 的初始状态为 (dp [S][k0].time = 0, 初始资源 = r_S)，其中 k0 为初始权限等级
2. 权限等级上限：根据总资源最大值确定权限等级的可能范围，避免状态空间过大
3. 节点资源处理：到达节点时立即收集其资源值并更新权限等级
4. 边的过滤：对于每个状态 (u, k)，只考虑 req ≤ k 的边，减少无效计算
5. 路径重构：通过前驱指针记录每个状态的来源，以便在找到最优解后重构路径

复杂度分析

• 时间复杂度：O (E × K × log (V × K))，其中 K 为最大权限等级数，V 为节点数，E 为边数
• 空间复杂度：O (V × K)，主要用于存储 dp 数组和优先级队列

通过合理设置 K 的上限（通常题目会保证 K 在可接受范围内），算法能够在规定时间内完成计算。

代码实现

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

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>using namespace std;const int MAX_NODES = 1005;
const int MAX_LEVEL = 20;    // Maximum possible permission level
const int INF_TIME = INT_MAX / 2;
const int INF_RESOURCE = INT_MAX / 2;// Structure to represent an edge
struct Edge {int to;           // Target nodeint time;         // Travel timeint req_level;    // Required permission levelint cost;         // Resource costEdge(int t, int tm, int rq, int c) : to(t), time(tm), req_level(rq), cost(c) {}
};// Structure to represent a node
struct Node {int resource;     // Resource value of this nodevector<Edge> edges;  // Outgoing edges
};// Structure to represent a state in priority queue
struct State {int node;         // Current nodeint level;        // Current permission levelint time;         // Accumulated timeint resource;     // Accumulated resource after collecting current nodeState(int n, int l, int t, int r) : node(n), level(l), time(t), resource(r) {}// For priority queue (min-heap based on time, then resource)bool operator>(const State& other) const {if (time != other.time) {return time > other.time;}return resource > other.resource;  // Lower resource is better for same time}
};// Structure to store DP state information
struct DPState {int time;         // Minimum time to reach this stateint resource;     // Minimum resource consumption for this timeint prev_node;    // Previous node for path reconstructionint prev_level;   // Previous level for path reconstructionDPState() : time(INF_TIME), resource(INF_RESOURCE), prev_node(-1), prev_level(-1) {}
};int main() {int n, m;               // Number of nodes and edgesint S, T, T_max;        // Start node, target node, maximum allowed timeint R;                  // Resource threshold for level upgrade// Read inputcin >> n >> m;cin >> S >> T >> T_max >> R;// Initialize nodesvector<Node> nodes(n + 1);  // 1-indexedfor (int i = 1; i <= n; ++i) {cin >> nodes[i].resource;}// Read edgesfor (int i = 0; i < m; ++i) {int u, v, t, req, c;cin >> u >> v >> t >> req >> c;nodes[u].edges.emplace_back(v, t, req, c);}// DP table: dp[node][level] = best state to reach node with given levelvector<vector<DPState>> dp(n + 1, vector<DPState>(MAX_LEVEL + 1));// Priority queue for modified Dijkstra's algorithmpriority_queue<State, vector<State>, greater<State>> pq;// Initialize starting nodeint initial_resource = nodes[S].resource;int initial_level = initial_resource / R;if (initial_level > MAX_LEVEL) initial_level = MAX_LEVEL;dp[S][initial_level].time = 0;dp[S][initial_level].resource = initial_resource;pq.emplace(S, initial_level, 0, initial_resource);// Process stateswhile (!pq.empty()) {State current = pq.top();pq.pop();int u = current.node;int k = current.level;int t = current.time;int r = current.resource;// Skip if we've found a better state alreadyif (t > dp[u][k].time || (t == dp[u][k].time && r > dp[u][k].resource)) {continue;}// If we've reached target, continue to find optimal solutionif (u == T) {continue;}// Explore all outgoing edgesfor (const Edge& edge : nodes[u].edges) {int v = edge.to;int travel_time = edge.time;int req_level = edge.req_level;int cost = edge.cost;// Check if current level is sufficient for this edgeif (k < req_level) {continue;}// Calculate new time and check if it exceeds maximum allowedint new_time = t + travel_time;if (new_time > T_max) {continue;}// Calculate new resource after using this edge and collecting target node's resourceint new_resource = r - cost + nodes[v].resource;if (new_resource < 0) {  // Not enough resource to use this edgecontinue;}// Calculate new permission levelint new_level = new_resource / R;if (new_level > MAX_LEVEL) {new_level = MAX_LEVEL;  // Cap the level to reduce state space}// Update state if this path is betterbool is_better = false;if (new_time < dp[v][new_level].time) {is_better = true;} else if (new_time == dp[v][new_level].time && new_resource < dp[v][new_level].resource) {is_better = true;}if (is_better) {dp[v][new_level].time = new_time;dp[v][new_level].resource = new_resource;dp[v][new_level].prev_node = u;dp[v][new_level].prev_level = k;pq.emplace(v, new_level, new_time, new_resource);}}}// Find the best solution among all possible levels at target nodeint best_time = INF_TIME;int best_resource = INF_RESOURCE;int best_level = -1;for (int k = 0; k <= MAX_LEVEL; ++k) {if (dp[T][k].time < best_time) {best_time = dp[T][k].time;best_resource = dp[T][k].resource;best_level = k;} else if (dp[T][k].time == best_time && dp[T][k].resource < best_resource) {best_resource = dp[T][k].resource;best_level = k;}}// Check if solution existsif (best_time == INF_TIME || best_time > T_max) {cout << -1 << endl;return 0;}// Reconstruct pathvector<int> path;int curr_node = T;int curr_level = best_level;while (curr_node != -1) {path.push_back(curr_node);DPState& state = dp[curr_node][curr_level];int next_node = state.prev_node;int next_level = state.prev_level;curr_node = next_node;curr_level = next_level;}reverse(path.begin(), path.end());// Output resultscout << best_time << " " << best_resource << endl;for (int node : path) {cout << node << " ";}cout << endl;return 0;
}

代码解析

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

1. 数据结构设计：

   • Edge结构体存储边的属性：目标节点、通行时间、所需权限等级和资源消耗
   • Node结构体存储节点的资源值和其 outgoing 边集合
   • State结构体表示优先队列中的状态，包含当前节点、权限等级、累计时间和资源
   • DPState结构体存储动态规划状态信息，包括最小时间、资源消耗和前驱节点信息

2. 核心算法实现：

   • 采用改进的 Dijkstra 算法，使用优先级队列按时间和资源消耗排序
   • 二维 DP 数组dp[node][level]跟踪到达每个节点在特定权限等级下的最优状态
   • 状态转移时考虑权限等级对边的访问限制，以及资源收集对权限等级的影响

3. 权限与资源管理：

   • 权限等级通过累计资源值计算：level = resource / R
   • 严格检查边的访问权限，只有当前等级足够时才能使用
   • 资源消耗和节点资源收集动态更新，并影响后续权限等级

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

   • 在目标节点 T 的所有可能权限等级中选择最优状态（时间最短，资源消耗最小）
   • 通过前驱指针重构完整路径
   • 若不存在满足约束的路径，输出 - 1

该算法通过扩展状态空间来处理权限等级的动态变化，既保证了找到最短时间路径，又在时间相同时选择资源消耗最小的方案，完美解决了题目的双重优化目标。

扩展思考

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

1. 引入权限等级的动态变化函数，使权限与资源的关系更复杂（如非线性关系）
2. 考虑节点的访问次数限制，增加问题的约束复杂度
3. 扩展为多源多汇问题，处理更复杂的网络结构
4. 加入时间窗口约束，要求在特定时间段内到达某些节点

这些扩展将进一步提高问题的难度，更全面地考察选手对图论算法和动态规划的综合应用能力。

通过本题的求解可以看出，现代算法竞赛题目越来越注重实际问题的建模能力，要求选手能够将现实中的约束条件转化为算法中的状态表示和转移规则，这需要扎实的算法基础和灵活的问题分析能力。