题解：P10533 [Opoi 2024] 热核武器

· · 题解

这题我们可以分成三个部分来解，得到框架代码。

part1

目标：把输入的数据转化成图。

直接按题意模拟即可。

part1 代码

part2

目标：求出 \gamma 值。

实现：题目要求这个城市走到首都的最小道路数，因为 N \le 500，所以我们有几种方法可以求最小道路数。

方法1：Floyd 算法。

这个算法代码很简洁，并且复杂度为 \mathcal{O}(n^3)，正好可以过。建议先完成 B3647。

Floyd 算法的流程：

  1. 定义 b_{i,j} 为从点 i 到点 j 的最短路径。
  2. 对于每一个节点 k，检查 b_{i,k}+b_{k,j}<b_{i,j} 是否成立，如果成立就令 b_{i,j}=b_{i,k}+b_{k,j}。

part2 Floyd 算法代码

方法2：Dijkstra 算法。

如过你想优化复杂度，那么这个方法非常合适，因为它的时间复杂度上限只有 \mathcal{O}(n^2)。

Dijkstra 算法的流程：

  1. 先初始化 dis_{0}=0，其它为无穷大。
  2. 找一个最小的 dis_{i}，此时 dis_{i} 已经是最小的，所以不可能有别的路径可以更新 dis_{i}。
  3. 找到所有与点 i 连接的点 j，如果通过这个点的路径更短，更新 dis_{j} 为 dis_{i}+i 到 j 的距离。
  4. 如果全部点都访问完毕，跳出循环，否则回到第 2 步。

part2 Dijkstra 算法代码

part3

目标：判断是否存在把 \gamma 分成两组的和相等。

实现：可以用 01 背包，背包的花费和价值都是 \gamma 值，算法复杂度是 \mathcal{O}(n^3)，可以过这题，那么 part3 部分的代码也实现了。

part3 代码

AC 代码