全部文章

页码5/11

重要的城市

本题要求在一张无向加权图中寻找所有重要城市：若摧毁某节点会导致至少一对其他节点之间的最短路径变长或不可达，则称该节点为重要城市。

在不超过背包容量 W 的前提下，从 n 种可无限次重复选择的物品中挑选物品（每种物品重量为 w_i，价值为 v_i），求能装入背包的物品总价值最大值。

给定 n 种数量有限（第 i 种最多取 c_i 个）的物品装入容量为 W 的背包中，要求在总重量不超过背包容量的前提下，使得装入物品的总价值最大。

将 n 种各只有一件的物品装入容量为 W 的背包中，每种物品只能选择装或不装，要求在总重量不超过背包容量的前提下，使得装入物品的总价值最大。

Bellman‑Ford 算法用于求解带负权边的单源最短路径，允许边权为负，通过对所有边执行 n‑1 轮松弛操作得到最短路径；再执行一轮松弛，若仍可更新距离，说明图中存在负权回路，时间复杂度 O (nm)，效率低于 Dijkstra，适合检测负权环。

松弛是最短路径算法里的核心操作，对于边 (u, v)，权值为 w，若 dist[v]>dist[u]+w，就更新 dist[v]=dist[u]+w，尝试找到顶点 v 的更短路径；Dijkstra、Bellman‑Ford、SPFA、Floyd‑Warshall 都基于松弛思想。

倍增法（Binary Lifting），核心思想是利用二进制拆分，预处理出跳 2⁰、2¹、2²… 步的状态，把单次大步查询拆解成若干次预计算的小步跳转，将原本线性的时间复杂度优化到对数级别，常用于 LCA、RMQ、后缀数组等问题。

动态规划是把大问题拆解成重复出现的子问题，保存子问题的计算结果避免重复运算，通过子问题最优解逐步推导出原问题最优解的算法思想，常用于计数、求最值类问题。