自动搬运

查看原文

来自洛谷，原作者为

	shuqiang 这个家伙不懒，但是什么也没有留下

搬运于2025-08-24 22:58:57，当前版本为作者最后更新于2024-05-29 13:35:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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 代码